[C++] Four Squares (백준 17626번)

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

 

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

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

    int n;
    cin >> n;
    vector<int> dp(n + 1, 100);

    dp[0] = 0;
    dp[1] = 1;
    for (int i = 1; i < 300; i++) {
        int sq = i * i;
        int idx = sq;
        while (idx < n + 1) {
            dp[idx] = min(dp[idx - sq] + 1, dp[idx]);
            idx++;
        }
    }

    cout << dp[n] << '\n';
}

"최소" 개수의 제곱수 합으로 표현해야 한다는 점에서 dp가 떠올랐다. 0부터 n까지 배열로 만들고 제곱수를 더해가며 dp 배열을 채웠다. (AC)