[백준] Four Squares

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

17626번: Four Squares

우선 문제부터 요약하면, 

자연수 n이 주어지면, 해당 숫자를 가장 적은 갯수의 제곱수의 합으로 표현하는 경우 총 몇개가 사용되는지를 출력해야 합니다. 

 

<Solution>

예를 들어서 10이라는 숫자가 있다면, 10에서 1, 4, 9를 뺀 9,6,1 을 만드는 경우의 수중 최소값 + 1이 최솟값이 될 것을 알 수 있습니다.

 

그래서 이렇게 dp table을 순차적으로 구성해서 계산하면 됩니다.

구현은 아래와 같습니다.

#include <iostream>

using namespace std;

int toMake;
int dpTable[50000+10];

int main(){
    cin >> toMake;

    // build dpTable
    for(int i = 1; i<=50000; i++){
        int tmpMin = 987654321;    
        int toSubtract = 1;
        while(i - toSubtract*toSubtract>=0){
            tmpMin = min(tmpMin, dpTable[i - toSubtract*toSubtract]+1);
            toSubtract++;
        }
        dpTable[i] = tmpMin;
    }
    cout << dpTable[toMake] << '\n';
    return 0;
}