BOJ 1699 제곱수의 합

boj 1699 제곱수의 합

수가 주어지면 그 수를 제곱수들의 합으로 표현할 때, 최소의 항 갯수를 구하는 문제이다.
모든 수는 1의 합으로 표현할 수 있기에 최대의 항 갯수는 입력된 수의 크기와 동일하다.
그러므로, 테이블 D[i]를 i를 제곱수의 합으로 표현할 때의 최소의 항 갯수라고 정의하면, D[i] = i 라고 초기 값을 지정해줄 수 있다.
최소의 항 갯수를 구하는 방법은 간단하다. i에서 i를 넘지 않는 제곱수를 빼면서 최소 항의 갯수를 변경해주는 것이다.
이를 점화식으로 나타내보자.

D[i] = min(D[i], D[i - 제곱수]+1)

이때, +1을 해주는 이유는 제곱수에 해당하는 항 갯수를 더해주는 것이다.

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

int n;
int D[100005];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) D[i] = i;

    for (int i = 4; i <= n; i++)
    {
        for (int j = 1; j * j <= i; j++)
        {
            D[i] = min(D[i], D[i - j * j] + 1);
        }
    }

    cout << D[n];
}