[백준] 17626번: Four Squares [C++]

 

알고리즘 분류: 다이나믹 프로그래밍, 브루트포스 알고리즘

문제 링크: https://www.acmicpc.net/problem/17626

17626번: Four Squares

 

 

【 풀이 】

 

DP 문제이다. 즉 규칙을 먼저 찾는 것이 중요한 문제.

n의 제곱수들의 최소 개수를 저장한 배열을 dp라고 가정하면, dp[n]은 항상 최적의 해가 된다고 볼 수 있다.

그리고 dp[제곱수]는 항상 그 값이 1이다.

 

• dp[1] =1
• dp[2] = dp[1] + dp[1]
• dp[3] = dp[1] + dp[2]
• dp[4] = 1
• dp[5] = dp[4] + dp[1]
• dp[6] = dp[4] + dp[2]
• dp[7] = dp[4] + dp[3]
• ....

위의 규칙으로 미루어보았을 때, 점화식은 dp[N] = dp[i*i] + dp[N - i*i]라고 볼 수 있다.

하지만 여기서 dp[99]의 경우를 살펴보자.

dp[99]는 다음과 같이 나눌 수도 있다.

 

• dp[1] + dp[98]
• dp[4] + dp[93]
• dp[9] + dp[90]
• dp[16] + dp[83]
• dp[25] + dp[74]
• dp[36] + dp[63]
• dp[49] + dp[50]
• dp[64] + dp[35]
• dp[81] + dp[18]

즉 위처럼 dp[N]을 나타내는 경우의 수가 여러 가지일 수도 있기에, 제곱수를 기반으로 모든 경우의 수 중에 최솟값을 저장해야 한다.

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int dp[50001];
int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i < 224; i++)
		dp[i * i] = 1;

	for (int i = 1; i <= n; i++)
	{
		int min = 10000;
		if (dp[i] != 1)
		{
			for (int j = 1; j <= sqrt(i); j++)
			{
				int a = dp[j * j] + dp[i - j * j];
				if (min > a)
				{
					min = a;
					dp[i] = a;
				}
			}
		}
	}
	cout << dp[n];
	return 0;
}