[C++] 백준 - 1699 : 제곱수의 합

문제 링크

1699번: 제곱수의 합

 

풀이 ) DP

  이 문제를 풀 때 memo[i]에 대해서 초기화를 할 때는 i 를 i-1과 1로 나눌 수 있으므로 memo[i-1] + 1로 한다.

  이후 2의 제곱인 4부터 시작해서 i에서 뺀 memo[i - j^2] + 1과 현재의 memo[i]를 비교하여 작은 값을 memo[i]에 저장한다.

  

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[100002] = {0, };

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; ++i){
        memo[i] = memo[i-1]+1;
        for(int j = 2; j*j <= i; ++j)
            memo[i] = min(memo[i], memo[i-j*j]+1);
    }
    printf("%d\n", memo[n]);
    return 0;
}