C++) 백준 1699번 풀이_제곱수의 합

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

1699번: 제곱수의 합

 

와

나는

해설을 보고 설명을 들어서 겨우 푸는데

이걸 걍 풀어내는 사람들은 대체.. 어떻게 푸는거지?

아니 이 문제를 만드는 사람은 어케 만드는거지?

 

무튼

 

ㅇㅁ..

어떻게 설명을 해야되지

 

일단 시작은 

모든 제곱수 (1, 4, 9, 16, 25 ...) 의 결과값은 1이라는 것부터 시작함

 

R[1] = R[4] = R[9] = R[16] = 1

 

이제 그 외의 수가 문젠데

맨 첨에 일단 나는 이렇게.. 시작함...

 

R[1] = 1 R[2] = R[1] + 1 R[3] = R[1] + 1 + 1 R[4] = 1 R[5] = R[4] + 1 R[6] = R[4] + R[2] R[7] = R[4] + R[3]  ....

그러나

그렇다

이렇게 생각하면 답도 없는 것이다!

 

43 = R[36] + R[7] > R[25] + R[18]

43 = 36 + 4 + 1 + 1 + 1 = 25 + 9 + 9 

 

이다 

최솟값을 구해야하는 건 알겠으니 이제 여기서 규칙을 찾아야 한다 !!

 

일단 R[제곱수] 는 무조건 1이다

 

그래서 결국 N에대한 제곱수의 합을 찾으라고 하면

N에서 제곱수를 뺀 수까지의 제곱수의 합에 + 1을 한 값을 구하게 된다.

 

R[N] = min( R[N - N까지의 제곱수] + 1)

 

그러니까 음

R[2] = R[1] + 1 => 2 R[4] = R[0] + 1 => 1   R[9] = R[9-9] + 1 => 1 R[18] = min( R[18-9] + 1 ) => 2 R[43] = min( R[43-36] + 1, R[43-25] + 1, R[43-16] + 1, ... ) => 3 ...

 

 

이런 느낌

을 코드로 짜면 됩니다.

 

#include<stdio.h>
#include<algorithm>
using namespace std;

int main(void) {
	int i, j, num ;
	int res[100001] = { 0 };

	scanf("%d", &num);
	
	for (i = 1; i <= num; ++i)
	{
		res[i] = i;

		for (j = 2; j * j <= i ; ++j)
		{
			if (i - j * j >= 0)
				res[i] = min(res[i - j * j] + 1, res[i]);
		}
	}

	printf("%d", res[num]);
}