[BOJ/DP] 백준 1699 - 제곱수의 합 (Java)

1699 - 제곱수의 합

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

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다
ex. 11 = $3^2 + 1^2 + 1^2$ (3개 항) = $2^2 + 2^2 + 1^2 + 1 ^2 + 1^2$ (5개 항)
수학자 숌크라테스는 "11은 3개의 항의 제곱수 합으로 표현할 수 있다"고 말한다
또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 최소 개수는 3개이다

=> 주어진 자연수 N을 제곱수들의 합으로 표현할 때 그 항의 최소개수?

입력: 자연수 N (1 <= N <= 100,000)
출력: 주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수

---

풀이

• `dp[i]`: i를 제곱수의 합으로 표현하는 데 필요한 최소 항의 개수
• `dp[i] = Math.min(dp[i], dp[i - j * j] + 1)`
  • `dp[i - j * j] + 1`: i에서 $j^2$를 사용하고 남은 수 + 1($j^2$)

---

코드

import java.io.*;

// 제곱수의 합
public class boj_1699 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            dp[i] = 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]);
    }
}