16. 제곱수의 합

입력

---

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 )  

출력

---

필요한 제곱 수의 최소 개수를 출력한다.

 

예제 입력

45

예제 출력

2

 

예제 입력

38

예제 출력

3

#include <stdio.h>
#include <algorithm>

using namespace std;

const int MAX = 100010;

int n;
int arr[MAX];
int d[MAX];

int main() {

  scanf("%d",&n);
  
  for(int i=0;i<=n;i++){
    d[i] = i;
  }
  
  for(int i=2;i<=n;i++){
    //printf("%d\n",i);
    
    for(int j=2;j*j<=i;j++){
      d[i] = min(d[i],d[i-j*j]+1);
      
      //printf("%d ",d[i]);
    }
    
    //printf("\n\n");
  }
  
  printf("%d",d[n]);
  return 0;
}