📖 [백준알고리즘 풀이] Q.1699 제곱수의 합 문제 풀이 - java

📖 문제

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

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=3^2+1^2+1^2(3개 항)이다.

이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=2^2+2^2+1^2+1^2+1^2(5개 항)도 가능하다. 이 경우,

수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의

제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

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

입력

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

출력

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

🔍 접근법

BOJ Q.11722 제곱수의 합 문제입니다.

동적프로그래밍으로 풀이가 가능 합니다.

주어지는 자연수를 제곱수의 합으로 나타날 때 해당 제곱수 항의 최소 개수를 구하는 문제입니다.

1 = 1^2

2 = 1^2 + 1^2

3 = 1^2 + 1^2 + 1^2

4 = 2^2

일 때

자연수 5에 대한 제곱수의 합은

2+3 또는 1+4 로 가능합니다 .

5 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2

5 = 2^2 + 1^2

로 가능한데 여기서 1+4의 경우인 2^2 + 1^2 가 항의 개수가 적습니다.

즉 5에 대한 제곱수의 합을 만들 수 있는 경우에서 최소 개수의 항으로만 구성되도록 하면 됩니다.

여기서 d[i] 배열은 각 자연수 i에 대한 제곱수의 합 최소 개수의 항으로 구성되어 있으므로 이 값들을 조합하면

주어진 자연수 N까지의 제곱수의 합의 최소 개수를 구할 수 있습니다.

d[i] = min(d[i],d[i-(제곱수의 합)] + 1)

💻 코드

package problem.dynamic;

import java.io.*;

public class Main_1699 {
    static int n;
    static int[] d;

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        solve();
        bw.write(Integer.toString(d[n]));
        bw.flush();
        bw.close();
    }

    public static void solve() {
        d[1] = 1;
        for(int i=2; i<=n; i++){
            d[i] = i;
            for(int j=1; j*j<=i; j++){
                d[i] = Math.min(d[i],d[i-(j*j)]+1);
            }
        }
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        d = new int[n + 1];
        br.close();
    }
}

Written on February 25, 2021