문제
https://www.acmicpc.net/problem/1699
풀이
처음에는 큰 수의 제곱을 빼주는 식으로 그리디하게 풀었는데 무조건 큰 수가 적은 항을 갖지 않음
반례) 12 = 3x3 + 1x1 + 1x1 + 1x1
= 2x2 + 2x2 + 2x2
✨DP는 메모리제이션을 이용하기 때문에 모든 문제를 한 번씩만 풀면 돼서 시간복잡도가 O(N)으로 매우 강력하다 !!
sol)
5의 제곱수 개수 = 4의 제곱수 개수 + 1의 제곱수 개수
6의 제곱수 개수 = 4의 제곱수 개수 + 2의 제곱수 개수
7의 제곱수 개수 = 4의 제곱수 개수 + 3의 제곱수 개수
dp[i] = i로 초기화
dp[2] = dp[1] + 1 = 2
dp[3] = dp[2] + 1 = 3
dp[4] = dp[3] + 1 = 4
= dp[0] + 1 = 1
dp[5] = dp[4] + 1
※ +1해주는 이유 : dp[5] = 2x2 + dp[1]을 의미하므로 2x2에 해당하는 항의 개수를 의미함
코드
#include <iostream>
using namespace std;
int dp[100001];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
dp[i] = i;
for (int j = 1; j * j <= i; j++) {
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
cout << dp[n];
return 0;
}
👩🏻💻