171019_1699_제곱수의 합

#include <iostream> using namespace std; int main() {     int N;     int dp[100001]={0};     cin >> N;     for(int i=1; i <=N ; i++)     {         for(int j=1; j*j <= i; j++)            if(dp[i]>dp[i-j*j]+1 || dp[i]==0)                dp[i]=dp[i-j*j]+1;     }     cout << dp[N]; }

 며칠 고민해도 접근이 어려워 다른 사람 코드를 봤다.

현재 dp값이 앞으로의 값보다 더 큰 건 당연, 그 기점 찾기 위한 조건 dp[i]>dp[i-j*j]+1