[백준] 1699 제곱수의 합

문제

어떤 자연수 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)

출력

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

 

접근 방법

43을 만드는 제곱 항은 [25(5^2), 16(4^2), 1(1^2), 1(1^2), 1(1^2)]과 [25(5^2), 9(3^2), 9(3^2)] 등 다양하게 존재한다. 하지만 이중 가장 적은 개수의 제곱 항을 사용하는 것을 찾아야 한다.

 

처음에 무턱대고 큰 수 부터 찾게 되면 [25(5^2), 16(4^2), 1(1^2), 1(1^2), 1(1^2)]이 되어 5가 출력될 것이다. 하지만 위에서 볼 수 있듯이 43을 입력하면 3이 출력되어야 한다. DP 문제는 반드시 규칙을 찾고 점화식을 만들어야한다.

 

43을 만들기 전 숫자를 K라고 가정하자. 그러면 아래와 같은 방정식을 나타낼 수 있을 것이다.

 

43 = K + A1 + A2 + ... An    (An는 0이상의 정수)

K = 43 - (A1 + A2 + ... An)

 

여기서 43을 만들기 위한 최소한의 제곱 항의 개수는 몇개일까?

 

고민할 것도 없이 1개이다.

 

지금까지 알 수 있는 것은 43이라는 숫자를 구성하는 제곱 항 중 하나인 K는 43에서 A라는 제곱 항 하나를 뺀 값이라는 것이다.

 

즉, 43 - 1*1, 43 - 2*2, 43 - 3*3, 43 - 4*4, 43 - 5*5, 43 - 6*6 중 하나의 값을 가질 수 있다는 것이다.

 

이를 바탕으로 D라는 배열이 임의의 숫자 i에 대해서 최소한의 제곱 항 개수를 담고있다고 가정하면 아래와 같이 나타낼 수 있다.

 

D[N] = Min(D[N}, D[N-A*A]+1)

소스 코드

 

import java.util.*;

public class Main{
    public static void main(String[] args){
       	Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt();
		int[] d = new int[N+1];
		
		for(int i=0;i<d.length;i++) {
			d[i] = i;
		}
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j*j<=i;j++) {
				d[i] = Math.min(d[i], d[i - j*j] + 1);
			}
		}
		System.out.println(d[N]);
    }
}