백준 17626 Four Squares c++ (dp)

문제 출처 : https://www.acmicpc.net/problem/17626

17626번: Four Squares

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 브루트포스 알고리즘

풀이

봐도 봐도 어려운 dp 문제.

문제가 dp인지 몰라서 어려운 dp 문제.

알고 나면 쉬운 문제.

dp 특이다..

우선 dp[i] = i를 최소 개수의 제곱 합으로 표현했을 때 개수

라고 하자.

그러면 dp[i]는 i에 대해 항상 최선의 값(최소 개수의 제곱 합)을 가지게 되며,

dp[i] = dp[a]+dp[b]도 항상 최선의 값을 가지게 된다.

dp[10]를 구해보자.

dp[10]은

dp[1]+dp[9]

dp[4]+dp[6]

중에서 가장 작은 값이 된다.

 

dp[50]을 구해보자.

dp[1]+dp[49]

dp[4]+dp[46]

dp[9]+dp[41]

dp[16]+dp[34]

dp[25]+dp[25]

dp[36]+dp[14]

중에서 가장 작은 값이 된다.

즉 점화식은 dp[n] = dp[i*i] + dp[n-i*i]이다.

dp[1], dp[4], dp[9] 등의 제곱수들은 모두 값이 1이므로 이러한 제곱수들이 기저 사례가 된다.

 

코드

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;

int dp[50001];
void makeDp(int num) {
	
	for (int i = 1; i*i <= num; i++) {
		if (dp[num] == 0) {
			dp[num] = dp[i*i] + dp[num - i*i];
		}
		else {
			dp[num] = min(dp[num], dp[i*i] + dp[num - i*i]);
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int size = sqrt(n);
	for (int i = 1; i*i <= n; i++) {
		dp[i*i] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if (dp[i] != 0) continue;
		makeDp(i);
	}
	cout << dp[n];
	return 0;
}