728x90
반응형
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];
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 가장 긴 바이토닉 부분 수열 (0) | 2020.11.03 |
---|---|
[algorithm] 백준 - 합분해 (0) | 2020.11.03 |
[algorithm] 백준 - 연속합 2 (0) | 2020.11.03 |
[algorithm] 백준 - 가장 긴 증가하는 부분 수열 1 & 4 (0) | 2020.11.03 |
[algorithm] 백준 - 스티커 (0) | 2020.11.02 |