[algorithm] 백준 - 제곱수의 합

DP문제이다.

 

어떤 자연수는 제곱수의 합으로 이루어져 있으며, 합을 이루는 가장 적은 항의 개수를 리턴하는 것이다.

 

자연수	제곱수의 합
1	1
18	(3개) 4^2 + 2 = 18 (2개) 3^2 + 3^2 = 18 ... 가장 적은 개수: 2개

제곱 수가 가장 큰 수와 상관 없이 적은 개수를 이루기 위해서는 모든 제곱수와 비교해서 적은 개수를 구해야한다.

 

따라서 제곱수에 해당하는 수는

제곱수 1개로 이루어져 가장 적은 수이므로 별도로 vector에 삽입하고,

if((int)sqrt(i) == sqrt(i)){
	dp[i] = 1;
    multiplyVector.push_back(i);
}

제곱수가 아닌 수는

삽입된 수 중 가장 적은 항으로 이룰 수 있는 경우를 찾아 DP에 삽입했다.

dp[i] = 987654321;
for(int j = 0; j < multiplyVector.size(); j++){
	dp[i] = min(dp[i], dp[multiplyVector[j]] + dp[i - multiplyVector[j]]);
}

가장 적은 항을 구하는 것이므로 초깃값을 가장 큰 값으로 설정했다.

 

따라서 코드는 이렇다.

// 제곱수의 합
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

int main(void){
    int n, dp[100001];
    vector<int> multiplyVector;
    cin >> n;
    for(int i = 1; i <= n; i++){
        if((int)sqrt(i) == sqrt(i)){
            dp[i] = 1;
            multiplyVector.push_back(i);
        }
        else{
            dp[i] = 987654321;
            for(int j = 0; j < multiplyVector.size(); j++){
                dp[i] = min(dp[i], dp[multiplyVector[j]] + dp[i - multiplyVector[j]]);
            }
        }
    }
    cout << dp[n];
}