[백준] 17626_Four Squares

[문제]: 17626번: Four Squares (acmicpc.net)

 

예를 하나 가지고 하나하나 따져보자. 첫 for문은 제곱수는 1개의 제곱수로 표현할 수 있으므로 그 부분을 처리한 것이고, 핵심은 2번째 for문이다. 먼저 dp[n]의 정의다.

\[dp[n]=\text{제곱수들의 합이 \(n\)인, 제곱수들의 최소 개수}\]

즉,

\(1=1^2\text{ 이므로 } dp[1] = 1,\)

\(5=1^2+2^2\text{ 이므로 } dp[5] = 2,\)

\(13=2^2+2^2+2^2+1^1\text{ 이긴 하지만, } 13=2^2+3^2\text{ 이기도 하다. 최소 개수이어야 하므로 }dp[13] = 2,\)

\(60=1^2+1^2+3^2+7^2\text{ 이므로 } dp[60] = 4\) 이다.

 

핵심은 한 숫자를 표현하기 위해서 여러 방법이 존재한다는 것이고, 그중에서 제곱 수의 개수가 최소가 되는 것을 찾아야 한다. 아래 코드가 정답이지만 여전히 직관적이지 않은 부분은, for문 안에서 모든 dp[i]가 최소 개수임을 보장하는지의 여부다. 그래서 그냥 예를 하나 두고 쭉 나열해볼까 한다.

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

vector<int> dp(50001, 0x7f7f7f7f);
int MinNumberOfSquares(int n)
{
	for (int i = 1; i <= n; ++i) {
		if ((int)pow((int)sqrt(i), 2) == i)
			dp[i] = 1;
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= (int)sqrt(i); j++) {
			dp[i] = min(dp[i], dp[j*j] + dp[i - j * j]);
		}
	}
	return dp[n];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	cout << MinNumberOfSquares(n) << '\n';
	return 0;
}