[Baekjoon] 17626번: Four Squares

🥅 문제

https://www.acmicpc.net/problem/17626

 

🔍 설계

 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있으므로, 그 자연수를 이루는 제곱수들의 수는 다이나믹 프로그래밍을 이용하여 구할 수 있다.

 

예를 들어, 61 = 5^2 + 6^2이므로 5^2의 최소 제곱수 개수인 1과 6^2의 최소 제곱수 개수인 1을 더해 제곱수 2개를 이용하여 구할 수 있다. 

 

👊 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n;
vector<int> dp(50001, 1e9 + 7);

int main(void)
{	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	
	dp[0] = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = 1; j * j <= n; j++) {
			if (i + j * j > n) {
				continue;
			}
			dp[i + j * j] = min(dp[i + j * j], dp[i] + 1);
		}
	}

	cout << dp[n] << "\n";

	return 0;
}

 

📝 메모

다이나믹 프로그래밍을 할 때는 항상 초깃값과 범위 설정에 유의해야 한다.