[ DP - 17626 ] Four Squares

 

문제

---

접근법

 

DP 문제이다 직접 해보자.

 

1 -> 1                       -> 1

2 -> 1 + 1                 -> 2

3 -> 1 + 1 + 1            -> 3

4 -> $2^2$                     -> 1 

5 -> $2^2 + 1$                -> 2 = 1 + DP[5- $2^2$ ]

6 -> $2^2 + 1 + 1$          -> 3 = 1 + DP[6-$2^2$]

 

약간 규칙이 보일 것이다.

자연수 N의 제곱으로 표현되는 1,4,9 등은 1개가 최소이다. N의 제곱으로 표현되지 않으면, 나와 가장 가까운 자연수 N의 제곱을 뺀 DP[] 값에 1을 더해주면 된다.

 

하지만 예외사항이 발생한다.

23의 경우 위 논리데로 수행하면 DP[23] = DP[7] + 1, DP[7] = DP[3] + 1 = 4이므로 DP[23]은 5이 된다. 이는 넷 혹은 그 이하의 자연수의 제곱의 합으로 표현할 수 없다.

 

우리가 간과한 것은 가능한 최소 경우의 수를 찾는 것이다. 23의 경우 1,4,9,16 총 4개의 자연수 N의 제곱이 존재한다. 따라서 이 4가지 모두 고려하였을 때 최소의 경우의 수로 선정해야 한다.

 

이제 구현해보자.

---

정답

#include<iostream>
#include<algorithm>
#include <limits.h>

using namespace std;

int32_t ars32_DP[50001];

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

	int32_t s32_Input, s32_I, s32_J, int32_Cnt = 2;

	cin >> s32_Input;

	ars32_DP[1] = 1;
	ars32_DP[2] = 2;
	ars32_DP[3] = 3;

	for (s32_I = 4; s32_I <= s32_Input; s32_I++)
	{
		if (s32_I == int32_Cnt * int32_Cnt)
		{
			ars32_DP[s32_I] = 1;
			int32_Cnt += 1;
		}
		else
		{
			int32_t s32_Tmp = INT_MAX;
			for (s32_J = 1; s32_J * s32_J < s32_I; s32_J++)
			{
				s32_Tmp = min(s32_Tmp, ars32_DP[s32_I - ((s32_J) * (s32_J))]);
			}
			ars32_DP[s32_I] = s32_Tmp + 1;
		}
	}

	cout << ars32_DP[s32_Input] << endl;

	return 0;
}