1699번. 제곱수의 합

 

아이디어

임의의 자연수 N 에 대해서 이게 제곱수들의 합으로 표현된다면

 

(N - 1) + 1

(N - 4) + 4

(N - 9) + 9

...

(N - X^2) + X^2

 

과 같이 다양한 방법이 있을 것이다.

 

따라서 dp[i] 를 i 를 제곱수의 합으로 표현할 때 그 항의 최소개수라고 정의한다면 아래와 같은 점화식을 얻을 수 있다.

 

dp[i] = min(dp[i - 1], dp[i - 4], dp[i - 9], ..., dp[i - X^2]) + 1

1   ≤   X   ≤   sqrt(i)

 

그리고 i 자체가 제곱수인 경우에는 dp[i] = 1 이 되어야 하므로 dp[0] = 0 으로 초기화 하면 된다.

 

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    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];
        Arrays.fill(dp, N);
        dp[0] = 0;
        dp[1] = 1;

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

        System.out.println(dp[N]);
    }
}