[백준] 제곱수의 합(1699번 JAVA) (!) / 400 - 다이나믹 프로그래밍 1

[백준] 제곱수의 합(1699번 JAVA) (!) / 400 - 다이나믹 프로그래밍 1

---

[접근 방법]

 

배열 DP 는 해당 인덱스를 제곱수의 합으로 나타낼 때, 그 제곱수 항의 최소 개수를 저장한다.

 

13을 예로 들겠다.

 

13 = 3^2 + 2^2 인 경우 항이 개로 최소 개수는 '2' 가 된다.

 

(13 - 1^2) , (13 - 2^2) , (13 - 3^2) 중 제곱수 항의 최소 개수 + 1 과 같다.

 

12 의 제곱수 식에 (+ 1^2) 를 하는 경우

9 의 제곱수 식에 (+ 2^2)를 하는 경우 

4 의 제곱수 식에 (+3^2)를 하는 경우

중 최소항의 개수를 가진 것을 고르면 된다.

 

(4^2 > 13 이므로 제외된다.)

 

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

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));

        // (1 ≤ N ≤ 100,000)
        int N = Integer.parseInt(br.readLine());
        
        int[] DP = new int[N+1];

        // 최댓값으로 초기화 , 1^2으로만 이루어짐.
        for(int i=1; i<=N; i++){
            DP[i] = i;
        }

        for(int i=1; i<=N; i++){

            for(int j=1; j*j <= i; j++){
                if (DP[i] > DP[i - j*j] + 1){
                    DP[i] = DP[i - j*j] + 1;
                }
            }
        }

        bw.write(DP[N] + "\n");
        bw.flush();
        bw.close();
    }
}