[BAE/<JOON> 문제풀이] 1699. 제곱수의 합 (DP.020)

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

1699번: 제곱수의 합

1/10

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n;
    vector<int> dp;
    cin >> n;
    dp.resize(n + 1);   

    for (int i = 1; i <= n; i++) {
        dp[i] = 100000;
    }

    for (int i = 1; i <= n; i++) {
        int p = 100000;
        for (int j = 1; j*j <= i; j++) {
            p = (p < dp[i - j * j] ? p : dp[i - j * j]);            
        }
        dp[i] = p + 1;
    }

    /*for (int i = 1; i <= n; i++) {
        cout << dp[i] << " ";
    }*/
    cout << dp[n] << endl;

    return 0;
}