[실전 문제] 제곱수의 합

1. 문제

숫자 N을 제곱수의 합으로 표현하고자 할 때, 사용해야 하는 제곱 수의 최소 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 숫자 45를 제곱수의 합으로 표현하고자 할 때 필요한 제곱 수의 최소 개수는 2개이며, 이는 다음과 같다.

45 = 3^2 + 6^2

---

입력

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

출력

필요한 제곱 수의 최소 개수를 출력한다.

예제 입력

case 1) 45

case 2) 38

예제 출력

case 1) 2

case 2) 3

 

 

 

2. 풀이

이 문제는 점화식을 만드는것이 핵심이다. 점화식을 구하는 순서는 다음과 같다.

• T(n) = T(a^2 + b^2 + c^2) = 3
• T(n-a^2) = T(b^2 + c^2) = 2
• 즉, T(n) = T(n-x^2) + 1

 

T(8) 일 경우,

• 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8개
• 2^2 + 1 + 1 + 1 + 1 = 5개
• 2^2 + 2^2 = 2개

 

일 때, 이 중 가장 최소가 되는 2가 답이 된다.

 

이 점을 이용하여 코드를 작성하면 다음과 같다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n+1];
        int sqrtX = (int) Math.sqrt(n); // dp[n] = dp[n-x^2] + 1

        for(int i = 1; i <= n; i++) {
            if(i == 1) {
                dp[i] = 1;
                continue;
            }
            for(int x = 1; x <= (int)Math.sqrt(i); x++) {
                if(i == x*x) dp[i] = 1;
                else {
                    if(dp[i] > 0) dp[i] = Math.min(dp[i], dp[i - x * x] + 1); // dp[i]에 값이 있을 경우
                    else dp[i] = dp[i - x * x] + 1; // dp[i]에 값이 없을 경우
                }
            }
        }

        bw.write(dp[n] + "");
        br.close();
        bw.flush();
        bw.close();
    }

}