05.08. 제곱수의 합 [Dynamic Programming][백준 1699]

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

1699번: 제곱수의 합

 

Algorithm classification : Dynamic Programming, Math

 

05.08.1. Problem

Any natural number N can be expressed as the sum of squares less than or equal to it. For example, 11=3^2+1^2+1^2 (3 terms). This expression can be expressed in several ways, and in the case of 11, 11=2^2+2^2+1^2+1^2+1^2 (5 terms) is also possible. In this case, the mathematician Sumcrates says, "11 can be expressed as the sum of the squares of three terms." Also, since 11 cannot be expressed as the sum of the squares of the terms less than that, the minimum number of square terms that can be expressed as the sum of 11 is 3.

Write a program to find the minimum number of terms when a given natural number N is expressed as the sum of squares.

 

05.08.2. Input limit

A natural number N is given in the first line. (1 ≤ N ≤ 100,000)

 

05.08.3. Output

When a given natural number is expressed as the sum of squares, the minimum number of squared terms is output.

 

05.08.4. Solution

문제를 읽어보시면 아시겠지만 바로 이전 포스팅에서 소개해드린 동전 2 문제와 같습니다. 동전 대신 제곱수를 사용하는 것이죠. 마찬가지로 제곱수는 배수관계에 있지 않으므로 Greedy algorithm으로는 해결할 수 없습니다. Buttom-up방식에서 반복문의 index를 활용하면 쉽게 해결할 수 있습니다. 물론 시간은 더 소요되겠지만 미리 제곱수를 계산해놓고 사용할 수도 있습니다.

	int dp[n*2];
	
	for(i = 0; i < n+1; i++){
		dp[i] = 1000000;
	}	
	
	for(i = 1; i < sqrt(n) + 1; i++){
		dp[i*i] = 1;
		for(j = i*i; j <= n; j++){
			dp[j] = min(dp[j], dp[j-i*i] + 1);
		}
	}
	
	printf("%d", dp[n] == 1000000 ? -1 : dp[n]);