BOJ 1699번

제곱수열 구하기

 

#include <iostream>

using namespace std;

int dp[100001] = {0,1,2};

int min(int a, int b){

    if(a < b) return a;

    else return b;

}

void makeRow(int num){

    for(int i = 2; i <= num; i++){

        dp[i] = i;

        for(int j = 1; j * j <= i; j++){

        dp[i] = min(dp[i], dp[ i - j * j] + 1);

        }

    }

}

int main(){

    cin.tie(NULL);

    ios_base::sync_with_stdio(false);

    int n;

    cin >> n;

    makeRow(n);

    cout << dp[n] ;

    return 0;

}