백준 1699: 제곱수의 합

각 수가 몇 개의 제곱 수 의합으로 이루어져있는지 푸는 문제, 다이나믹 프로그래밍을 이용해 이전 값을 저장하고 점화식을 세워가며 풀면 쉽다.

핵심은 7 = 1 + 1 + 1 + 4 라고 되있을 때 마지막 4이다. for문을 제곱으로 증가시켜가며 최소값을 찾고 그 값에 1을 더해준다.

#include <iostream>
#include <algorithm>
using namespace std;
int d[100050];
 
int main()
{
    int input = 0;
    cin >> input;
    for (int i = 1; i <= input; ++i)
    {
        int val = d[i - 1];
        for (int j = 2;j*j <= i; ++j)
            val = min(val, d[i - j*j]);
        d[i] = val + 1;
    }
    cout << d[input] << endl;
    return 0;
}