Baekjoon17626-Four Squares

백준 사이트 17626 - Four Squares 문제입니다.

---

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다. 백준에서는 Sliver5의 난이도를 책정하고 있습니다.
저는 어렵게 생각했으므로 Sliver5보다 높게주고 싶습니다..

---

4. 생각한 것들

• 0.5초 내로 값을 도출해내야하기 때문에 경우의 수를 다 따져가며 도는것은 불가능합니다.
• 5만 이하의 모든 수가 4개 이하의 제곱수로 표현이 된다는 것은 이미 증명되었으므로 이것을 이용해야합니다. 따라서 4보다 큰 경우는 생각안해도 됩니다.
• 1에서 5만까지 갈수록 결국 모든 수는 그 보다 작은 제곱수들로 표현됩니다. 어떤 수는 결국 어떠한 제곱수들로 표현되기 때문이죠.

따라서 해당 수가 원래 제곱수인지, 제곱수에서 어떤 제곱수를 더한 수인지만 판별하면 됩니다.

---

5. code

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

int dp[50001] = { 0,1,0 };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 1; i <=n;++i)
	{
		if ((int)sqrt(i) * (int)sqrt(i) == i) 
			dp[i] = 1;//제곱 수는 1
		else
			dp[i] = 500;// 턱없이 크게함. 5이상이면 뭐든 ok
	}
	for (int j = 1; j <= n; ++j)
	{
		for (int k = 1; k <= (int)sqrt(j); ++k)
		{
			dp[j] = min(dp[j], dp[k * k] + dp[j - k * k]);
		}
	}
	cout << dp[n];
}

---

6. 후기

이 문제가 왜 sliver5인지 알거 같기도하면서도 모르겠다.