DP [백준 1699 제곱수의 합] -java-

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

1699번: 제곱수의 합

제곱수들의 합으로 이루어지려면 N에서 제곱수를 빼어도 제곱수이어야 한다는 소리이다. 

 
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] dp = new int[num + 1];
 
        for (int i = 1; i <= num; i++) {
            dp[i] = i;
            for (int j = 1; j * j < i; j++) {
                if (dp[i] > dp[i - j * j] + 1) {
                    dp[i] = dp[i - j * j] + 1;
                }
            }
        }
        System.out.println(dp[num]);
 
    }
 
}