알고리즘 :: 백준 :: DP :: 1699 :: 제곱수의 합

문제

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

문제접근

1. N을 제곱수들의 합으로 표현했을 때, 마지막으로 오는 수를 i라고 가정하자. 이때 i의 범위는 $0 \leq i \leq \sqrt n$ 이다.
2. 점화식 $D(n) = min(D(n), D(n-i^2)+1)$이다.
3. 점화식을 그대로 코드로 옮긴다.

코드

#include <iostream>
using namespace std;

int N;
int dp[100001];

int solve(int num) {
    for (int i = 1; i <= num; ++i) {
        dp[i] = i;    // 1의 제곱으로만 이루어진 경우 = 최대값
        for (int j = 1; j * j <= i; ++j)
            dp[i] = min(dp[i], dp[i - j * j] + 1);
    }
    return dp[num];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    cout << solve(N) << '\n';
}

결과