BOJ[백준] - 1699 - 제곱수의 합

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

 

 

 

#include <cstdio>
 
int dp[100001];
int main()
{
   int n;
   scanf("%d", &n);
   for (int i = 1; i <= n; i++) {
      dp[i] = i;
      for (int j = 1; j*j <= i; j++) {
         if (dp[i] > dp[i - j*j] + 1) {
            dp[i] = dp[i - j*j] + 1;
         }
      }
   }
   printf("%d", dp[n]);
   return 0;
}