백준 1699 자바 - 제곱수의 합

문제

---

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

1699번: 제곱수의 합

 

 

 

문제해결

---

- 11일 경우

1^2 + 1^2 + 1^2..... : 11개

(j=1) dp[10] + 1^2 : (dp[10]+1) 3개

(j=2) dp[7] + 2^2 : (dp[7] + 1) 5개

(j=3) dp[2] + 3^2 : (dp[2] + 1) 3개

이 중 최소값인 3이 정답

import java.util.Scanner;

public class B1699_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] dp = new int[n+1];
        for (int i = 1; i <= n; i++) {
            dp[i] = i;//어떤 수든 1^2 + 1^2..... i개가 될 수 있다
            for (int j = 1; j*j <= i; j++) {//i보다 작은 제곱수들 비교
                //그중에서 가장 작은 값을 구한다
                dp[i] = Math.min(dp[i], dp[i-j*j] + 1);
            }
        }
        System.out.println(dp[n]);
    }
}