[Java] 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)

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

문제 풀이

몇가지를 생각해봐야한다.

1. 1, 4, 9, 16 ~~ 등등 특정 숫자는 최소 제곱수가 1이다. 

2. 숫자 N이 주어졌을 때 1 ~ N-1의 제곱수 항의 최소 개수를 활용해야한다.

 

1 ~ N 까지의 수 중 제곱수인 수 + (n - 제곱수) 의 최소 제곱수 갯수 중 최소인 값을 구하면 된다.

 

dp[1]  =  1  => 1^2

dp[2]  =  2  => 1^2 + 1^2

dp[3]  =  3  => 1^2 + 1^2 + 1^2

dp[4]  =  1  => 2^2

dp[5]  =  2  => 1^2 + 2^2

dp[6]  =  3  => 1^2 + 1^2 + 2^2

dp[7]  =  4  => 1^2 + 1^2 + 1^2 + 2^2

dp[8]  =  2  => 2^2 + 2^2

dp[9]  =  1  => 3^2

dp[10]  =  2  => 1^2 + 3^2

 

7로 예를 들어보자 1 ~ 7까지의 수 중 제곱수 인 것은 1과 4가 있다. 이 두 숫자의 최소 제곱수는 1이다

7 - 1 = 6, 7 - 4 = 3 >>>> 6과 3 중 최소 제곱수가 최소인 값을 골라서 +1 해주면 된다.

6 - 1 = 5, 6 - 4 = 2 >>>> 5와 2중 최소 제곱수가 최소인 값 + 1

5 - 1 = 4, 5 - 4 = 1 >>>> 4와 1중 최소 제곱수가 최소인 값 +1

4 - 1 = 3

3 - 1 = 2 

2 - 1 = 1 

 

N보다 낮은 최소 제곱수가 1인 숫자를 N 에서 뺀 뒤 나온 숫자를 같은 방식으로 계속 빼주고 뺀 횟수를 더해주면 답이되는 것.

 

이를 위해 반대로 낮은 수인 1부터 최소 제곱수를 구하면서 7을 구해보자

자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class SumSquareNumber {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int d[] = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            d[i] = i;
            for (int j = 1; j * j <= i; j++) {
                if (d[i] > d[i - j * j] + 1)
                    d[i] = d[i - j * j] + 1;
            }
        }
        // 1 1 -> d[1] = 1, d[1] > d[1 - 1] + 1 = 1 > 0 + 1, d[1] = 1
        // 2 1 -> d[2] = 2, d[2] > d[2 - 1] + 1 = 2 > 1 + 1, d[2] = 2
        // 3 1 -> d[3] = 3, d[3] > d[3 - 1] + 1 = 3 > 2 + 1, d[3] = 3
        // 4 1 -> d[4] = 4, d[4] > d[4 - 1] + 1 = 4 > 3 + 1
        // 4 2 -> d[4] = 4, d[4] > d[4 - 4] + 1 = 4 > 0 + 1, d[4] = 1
        // 5 1 -> d[5] = 5, d[5] > d[5 - 1] + 1 = 5 > 1 + 1, d[5] = 2
        // 5 2 -> d[5] = 2, d[5] > d[5 - 4] + 1 = 2 > 1 + 1
        // 6 1 -> d[6] = 6, d[6] > d[6 - 1] + 1 = 6 > 2 + 1, d[6] = 3
        // 6 2 -> d[6] = 3, d[6] > d[6 - 4] + 1 = 3 > 2 + 1
        // 7 1 -> d[7] = 7, d[7] > d[7 - 1] + 1 = 7 > 3 + 1, d[7] = 4
        // 7 2 -> d[7] = 4, d[7] > d[7 - 4] + 1 = 4 > 3 + 1

        System.out.println(d[n]);
    }
}