[백준 C++] 17626 Four Squares - 다이나믹프로그래밍

17626번: Four Squares

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

int DP[50001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	for (int i = 1; i <= N; ++i)
	{
		int MinCount = INT_MAX;
		for (int j = 1; j <= sqrt(i); ++j)
		{
			int CurrentNumber = j * j;
			if (CurrentNumber == i)
			{
				DP[i] = 1;
				break;
			}

			int Count = DP[i - CurrentNumber] + 1;
			if (Count < MinCount)
			{
				DP[i] = Count;
				MinCount = Count;
			}
		}
	}

	cout << DP[N];
}

---

 

다이나믹 프로그래밍 & 브루트포스 알고리즘으로 푸는 문제입니다.

 

1, 4, 9, 16, ... 등의 제곱수들의 해는 1이고, 최종적으로는 N의 해의 최소값을 구해야 하기 때문에

N 보다 작은 제곱수 하나를 선택한 경우(1 + DP[N - 해당제곱수])들 중에서 가장 작은 값을 선택하도록 해야 합니다.

따라서 바텀-업 방식으로 1부터 N까지 i를 1씩 증가시켜서 DP 배열을 채워주는데

다음과 같은 방식을 사용합니다.

 

1. i가 제곱수인 경우, 해는 1

2. i가 제곱수가 아닌 경우, i 보다 작은 제곱수 중 하나를 선택한 경우들 중 최소값 선택

 

ex. i 가 15인 경우,

i 보다 작은 제곱수: { 1, 4, 9 }

위의 제곱수 중 하나를 선택한 각각의 경우: { DP[14] + 1, DP[11] + 1, DP[6] + 1 }

위의 세 개의 값 중에서 최소값이 i의 해가 됩니다.