1699 제곱수의 합

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

1699번: 제곱수의 합

제곱수의 합 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

20783

8560

6313

41.052%

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

 

 

<풀이>

 

1. D[N] 은 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수 라고 일단 정의.

 

a1^2  +  a2^2  + a3 ^3 + .... + L^2 = N; 이라고 한다면

 바로 이전의 항의 식은 N-L^2 이 될것이다.

 

따라서 D[N-L^2] 에 +1 을 해주면 D[N]을 구할 수 있는데 최소갯수이므로

D[N] = min(D[N-L^2]+1 , D[N]) 을 해준다.

 

2. 초기값은  N = 1^2 + 1^2 +1^2 ..... (N개) 가되므로 

D[N] = N으로 초기화 해준다.

 

3. 나머지는 구현

 

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

int d[100001];
int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; ++i)
	{
		d[i] = i;
		
		for (int k = 1; k*k <= i; ++k)
		{
			d[i] = min(d[i - k * k] + 1, d[i]);
		}
	}

	cout << d[n] << '\n';
	return 0;
}