⭐️ 숫자 n
을 만드는데 필요한 제곱수 구하기(최대 4개)
n
보다 작은 수 중에 가장 큰 제곱수는 무조건 포함한다고 생각했기 때문에 dp[n] = dp[n-(n보다 작은 수 중 가장 큰 제곱수)]+1
로 풀이
솔루션 도출이 잘못 되었음.
이 방법으로 할 경우, 어떤 수에서는 제곱수의 개수가 4를 넘어가는 경우 발생
⭐️ 숫자 n
보다 작은 제곱 수 중에 dp[n - 제곱 수] 가 가장 작은 값
+ 1을 dp[n]
으로 설정
dp[제곱수]=1
로 세팅dp[n - 제곱수]
가 가장 작은 값을 dp[n]
으로 지정#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
vector<int> dp(n+1,0);
vector<int> square;
for(int i=1;i*i<=n;i++) {
square.push_back(i*i);
dp[i*i]=1;
}
for(int i=1;i<=n;i++) {
if(dp[i]==1) continue;
int mx=5;
for(int j=0;j<square.size();j++) {
if(square[j]>i) break;
mx=min(mx,dp[i-square[j]]);
}
dp[i]=mx+1;
}
cout << dp[n];
}