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

📌백준 1699 제곱수의 합
https://www.acmicpc.net/problem/1699

처음에는 가장 큰 제곱수를 먼저 빼고 시작하는게 제곱수 항의 최소 개수가 나오는거라고 생각했다. 예제가 다 맞아서 코드를 제출했더니

틀렸다

반례가 있었다. 32를 생각해보자.
나) 32 = 5^2 + 2^1 + 1^2 + 1^2 + 1^2 : 5
정답) 32 = 4^2 + 4^2 : 2

N에서 i의 제곱을 뺐을 때 0이 되지 않는 선에서
나올 수 있는 모든 개수 중 최소(min)가 되는 값을 구해줘야 한다.

d[i] = min( d[i], d[i-jxj] + 1 )
+1을 해주는 이유는 d[i-j*j]에서 제곱수를 한번 썼기 때문

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

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

    int dp[100001];
    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];
}