백준 1699 - Java

 

 

입력을 7을 하였을때, 출력이 4가 나와야한다. 이것이 어떻게 된 것인지 고민을 해보았는데 7 = 1^2 + 1^2 + 1^2 + 2^2 이렇게 1^2 이 3개와 2^2이 1개 총 4개가 나오게 된다면 7이 될 수 있다. 

이것도 최소갯수를 구해야하고 이전것과 비교하려면 동적 계획법을 사용할 수 있다.

 

import java.util.Scanner;

public class SumOfSquares {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[N+1];
//        dp[0] = 0;
//        dp[1] = 1;
        //dp값 입력해놓기.
        for (int i = 1; i <= N; i++) {
            dp[i] = i;
        }

        for (int i = 2; i <= N; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        System.out.println(dp[N]);
    }
}