📜 문제 이해하기
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5²과 1²의 합이다; 또한 4² + 3² + 1²으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125² + 6² + 1² + 1²라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105² + 15² + 8² + 5².
자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.
💡 문제 재정의
숫자를 최소 갯수의 제곱수로 표현해라.
✏️ 계획 수립
1부터 N까지 최소 제곱수를 순서대로 구해가면 된다. 이 때 이미 계산한거는 다시 구할 필요없이 동적 계획법을 통해 값을 구한다.
만약 값이 46이라면 46은 아래의 값들이 존재할 것이다.
46 = 1² + 45
46 = 2² + 42
46 = 3² + 37 ...
따라서 46의 최소 제곱수의 합은 1 + dp[45] or 1 + dp[42] or 1+ dp[37] ...
이런식으로 서술할 수 있다. 이 값을 모두 구해서 가장 작은 개수를 저장해가면서 나가면 된다.
💻 계획 수행
#include <bits/stdc++.h>
using namespace std;
int main() {
int dp[50001];
dp[1] = 1;
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int num;
cin >> num;
for (int i=1; i<=num; i++){
dp[i] = dp[1] + dp[i-1];
for (int j=2; j*j<=i; j++)
dp[i] = min(dp[i], 1 + dp[i-j*j]);
}
cout << dp[num] << '\n';
}🤔 회고
동적 계획법을 통해 풀 수 있는 문제였다. 동적 계획법은 점화식을 세우는 것이 가장 힘들고 역시 나에게 제일 어려운 알고리즘이었다. 계속 연습을 통해 익숙해지도록 노력해보자.
