17626 FourSquares C++ 백준

 

비슷한문제

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

 

다이나믹 프로그래밍이다 

제일 못하는것중에 하나 ㅠㅠ..

 

일단 제곱이 되는 것들은 d에서 1을 다 넣어주고 시작했다.

 

 

for (int i = 0; i <= n; ++i)
	{
		d[i] = 47483647;
	}

	for (int i = 1; i <= n; ++i)
	{
		if (i * i > n)
			break;
		d[i * i] = 1;
	}

 

그런다음에 d값은 높은 제곱에 있는 d값을 먼저 뺴주고 이후 d값은 낮은값은데 이미 저장되있는 값이다.

처음에 엄청 해매고 뭔말인지 몰랐는데 이 한줄설명이 끝인것같다. 

 

하지만 이런방식으로 풀면 오히려 높은 값이 나오게되는데

23는 16, 7 즉 16,4,1,1,1 인데

다른 방법인 9,9,5  즉 9,9,4,1 이 더 작다.

위의 계산식으로 하게되면 d[9]+d[14]가 나오게되는데 d[14]는 23돌기전에 구해져있으므로 정답이 나온다.

 

적은값을 넣어야되고, 만약 제곱으로도 구해지는 값이면 이미 1로 초기화가되있다.

그래서 min도 넣어줬다

 

 

코드

#include <iostream>
using namespace std;
int d[50001];

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i <= n; ++i)
	{
		d[i] = 47483647;
	}

	for (int i = 1; i <= n; ++i)
	{
		if (i * i > n)
			break;
		d[i * i] = 1;
	}
	
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j * j <= i; ++j)
		{
			
			d[i] = min(d[i], d[j * j] +d[i-j*j]);
		}
	}
	cout << d[n];
}