백준 1699번 - 제곱수의 합 [DP/자바 JAVA]

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

 

백준 1699번

 

---

 

---

결론 

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int dp[] = new int [100001];
        
        for(int i=0; i<=100000; i++){
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 1;
        
        for(int j=5; j<=n; j++){
            for(int i=1; i*i<=j; i++){
                if(i*i <= j){
                    dp[j] = Math.min(dp[j], dp[j-i*i]+1);
                }
            }
        }
        System.out.println(dp[n]);
    }
}