3장 다이나믹 프로그래밍 - (5) 문제 풀이 1 [1699번 - 제곱수의 합]

d[n] : n을 n보다 작은 제곱수들의 합으로 나타냈을 때, 최소항의 개수

n을 n보다 작은 제곱수들의 합으로 나타내면

n = ? + ? + ? + x^2 

마지막 항이 1^2, 2^2, 3^2, ...,  x^2 이 나올 수 있다.

이 때, 

d[n] = min(d[n-x^2] + 1) 이 된다.

여기서 x^2<= n 이므로 , x<= 루트n

채워야할 칸의 갯수는 n 개 이고, 각 칸마다 루트n 의 시간이 걸리므로, 시간 복잡도는 O(n*루트n)

-소스 코드

#include <iostream>

using namespace std;

int d[100001];

int main(void){

    int n;

    cin >> n;

    

    for(int i=1;i<=n;i++){

        d[i]=i;

        for(int j=1;j*j<=i;j++){

            if(d[i]>d[i-j*j]+1){

                d[i]=d[i-j*j]+1;

            }

        }

    }

    cout << d[n] << endl;

    return 0;

}