백준 1699번 - 제곱수의 합

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

1부터 N까지 모두 제곱수의 합으로 나타낼 수 있다.

모든 항목을 1의 제곱수의 합으로 채운다면 숫자의 크기가 곧 경우의 수가 될 것이다.

먼저 dp[i]는 i를 제곱수의 합으로 나타내는 경우라고 할 때

1로만 더해서 i값을 만든다면 경우의 수는 i가 될 것이다.

그리고 1부터 시작해서 어떤 수를 제곱했을 때 i에 가장 가까운 수를 n이라고 했을 때

dp[i]=min(dp[i],dp[i-n*n]+1)로 나타낼 수 있다.

예를 들어, dp[5]의 경우

dp[5]=dp[5-1*1]+1 (dp[4]인 경우에 1을 제곱한 값을 더한 경우)

dp[5]=dp[5-2*2]+1 (dp[1]인 경우에 2를 제곱한 값을 더한 경우)

...

로 나타낼 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
 
    int N;
    cin>>N;
    
    vector<int> dp(N+1,0);
    
    for(int i=1;i<=N;i++){
        
        dp[i]=i;
        for(int j=1;j*j<=i;j++)
            dp[i]=min(dp[i],dp[i-j*j]+1);
        
    }
    
    cout<<dp[N]<<endl;
    
    return 0;
}