1699번 제곱수의 합

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>

#include<math.h>

#define N 100001

int dp[N],basic = 0;

void dynamicP(int a)

{

for (int i = 1; i <= a; i++)

{

int c = pow(basic, 2);                

if (i == pow(basic+1, 2))             //  1 or 4 or 9 or 16같은 제곱수는 바로 1을 넣어버림 . 

{                                            // basic은 1 or 4 or 9를 찾을 때 쓰는 변수이다.

dp[i] = 1;

basic++;

continue;

}

dp[i] = dp[c] + dp[i-c];               // 탐욕 알고리즘처럼 일단 바로바로 최선의 최소개수를 넣고

for (int j = 1; j <= i / 2; j++)

{

if (dp[i] > dp[i - j] + dp[j])            // 탐욕은 각각의 선택에선 최선이지만 전체적으론 최선이 아닐수도 있으니

dp[i] = dp[i - j] + dp[j];        // 조건을 주어 최적의 해를 찾아줌

}

}

}

int main()

{

int a;

scanf("%d",&a);

dynamicP(a);

printf("%d",dp[a]);

return 0;

}