Problem Solving/Java

백준 1699 제곱수의 합 동적계획법 활용 풀이 ( Java )

TakeKnowledge 2019. 11. 1. 15:54
반응형
 

1699번: 제곱수의 합

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        // 142를 넣으면 3이 나와야 한다
        int[] d = new int[n + 1];
        // 최소 갯수 저장할 배열 변수
        // d[n] = n을 제곱수들의 합으로 표현할 때 그 항의 최소 갯수
        // d[n] = d[n-i^2] + 1 (마지막에 어떤수의 제곱이 올 때 = (i^2)항이 하나니까 1) 
 
        for (int i = 1; i <= n; i++) {
            // i부터 n까지
            d[i] = i;
            // i가지 있다고 초기화 하고 시작 ( 모든 수는 1^2의 합만으로 나타낼 수 있으니!  )
            for (int j = 1; j * j <= i; j++) {
                // 제곱의 수가 N보다 클수는 없으니 i (N) 까지 반복하며
                if (d[i] > d[i - j * j] + 1) {
                    // d[i]와 d[i - j * j] + 1 비교해서 작으면
                    d[i] = d[i - j * j] + 1;
                    // 최소 갯수 변경
                }
            }
        }
 
        bw.write(String.valueOf(d[n]));
 
        bw.flush();
 
    }
 
}
 
반응형