숫자 n 이 주어졌을 때, 완전제곱수의 합으로 표현할수 있는 최소 갯수는?

우선 "최소"를 물어본데다, 최적해가 없어 보이고(자료구조해도), DP가 될 것 같아 보이니까 완전탐색에서 시작해서 DP로 캐핑해보자.

그냥 완전탐색을 생각해 보면, 본인보다 작은 모든 완전제곱수를 1 ~ 최대 갯수만큼 채우면서 재귀를 돌려보자.

int findmin(int n, int curr, int total){

if(curr==0) return 0;

int ret = INT_MAX;

for(int i = 0 ; curr*i<=n ; i++){

ret = min(ret, i+findmin(n-curr*i,curr-1,total));

}

return ret;

}

time complexity : 함수실행 N * sqrt(N), 실행당 대량 sqrt(N) 회 수행 >> O(N^2) 알고리즘 쯤 될듯.