백준 1699 제곱수의 합 (C++)

1699번: 제곱수의 합

간단하게 접근했다가 생각을 많이하게된 문제이다. 자연수 N의 제곱수의 합의 최소 개수를 구해야한다. dp 배열은 각 숫자의 최소 개수를 나타낸다.
예를 들어보자.

• N = 5 라고 하면 최소 개수는 5 - 2 * 2를 하면 1이므로 N = 1 의 최소 개수 + 1
• N = 6 이라고 하면 최소 개수는 6 - 2 * 2 를 하면 2이므로 N = 2 의 최소 개수 + 1
• N = 11 이라고 하면 최소 개수는 11 - 3 * 3 을 하면 2이므로 N = 2 의 최소 개수 + 1
• 즉 dp[N] = dp[N - 제곱수] + 1

N = 1, 4, 9 와 같이 제곱수 그 자체인 수도 있으니 결과적으로 점화식은 아래와 같다.

dp[N] = min(dp[N], dp[N - 제곱수] + 1)

반복문을 돌면서 최소 개수를 구하게되고 결과적으로 답은 dp[N]에 저장된다.
개인적으로 아이디어가 잘 떠오르지 않은 문제였다. dp문제를 더 풀어봐야겠다.

---

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int dp[100001];

void solution() {
    for (int i = 0; i<= N; i++) {
        dp[i] = i;
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }

    cout << dp[N];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    solution();

    return 0;
}