[백준 C++] 17626 : Four Squares

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

DP와 브루트포스를 사용하는 문제이다.

 

모든 수는 제곱수로 표현되기 때문에 접근을 다음과 같이 진행하였다.

26일 경우는 1^2 + 25, 2^2 + 22 ...

그렇게 수를 계산하면 남은 숫자 25, 22 등등이 생기는데, 그것은 다시 DP[25], DP[22] 등을 다시 진행하면 된다.

 

모든 제곱수를 수를 확인하였을 때, 가장 적은 수를 계속 저장하면서 값을 확인하면 된다.

---

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main()
{
	vector<int> list;
	int n;
	cin >> n;

	list = vector<int>(n + 1, -1);
	
	for (int i = 1; i * i <= n; i++)
		list[i * i] = 1;
		

	for (int i = 1; i <= n; i++)
	{
		if (list[i] == -1)
		{
			int min = INT_MAX;

			for (int j = 1; j * j <= i; j++)
			{
				int current = list[j * j] + list[i - (j * j)];

				if (current < min)
					min = current;
			}

			list[i] = min;
		}
	}

	cout << list[n] << '\n';

	return 0;
}

n을 입력받은 뒤, n보다 낮은 제곱수들은 미리 넣어주는 작업을 진행한다.

 

위에서 설명했던 접근방법을 진행한 후, 낮은 min값을 찾아 값을 저장한다.