[C++] 백준 1699 제곱수의 합

1699 제곱수의 합

1699번: 제곱수의 합

C++

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

typedef long long ll;

int DP[100003] = {0, };

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

    for(int t=1; t<=n; t++) {
        for (int k = 1; k * k <= t; k++) {
            if(DP[t]==0) DP[t]=DP[t - k * k] + 1;
            else DP[t] = min(DP[t], DP[t - k * k] + 1);
        }
    }
    cout << DP[n] <<'\n';

    return 0;
}

 

작은 수부터, DP 값을 채워나간다.

만약 DP[t]가 0이라면, (아직 채워지지 않았다면), 초기화를 진행하고

그렇지 않은 경우에는 가능한 DP 경우 중 최솟값을 저장한다.