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

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 본 문제는200 7 ICPC Seoul Nationalwide Internet Competition E번 문제로 주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제다. 그렇기 때문에 자연수 N의 최소개수를 구하려면 이전에 N-x^2의 최소개수를 알아야 한다. 큰 문제를 작은문제로 구할 수 있기 때문에 DP로 풀 수 있으며, 점화식은 (1 ≤ x^2 < n) d[n] = min(d[n-x^2]) + 1으로 정의된다.

Bottom-up

#include <cstdio>
 
using namespace std;
 
int main() {
    int d[100001];
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        d[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j*j <= i; j++) {
            if (d[i] > d[i-j*j] + 1) d[i] = d[i-j*j] + 1;
        }
    }
    printf("%d", d[n]);
}