[백준] 1699 제곱수의 합 - Dynamic Programming / Java

• 문제 링크

1699번: 제곱수의 합

 

• 풀이 과정

각각의 자연수 n 의 최대 제곱수의 갯수는 n 이므로, 반복문을 통해 제곱수의 최대 개수를 초기화한다.(dp[i] = i)

 

1 ~ 3 은 제곱수의 최솟값 또한 1 ~ 3 이며,

나머지는 아래와 같이 구할 수 있다.

n	제곱수	점화식	개수
dp[4]	2^2	dp[4 - 2^2] + 1 = dp[0] + 1	1
dp[5]	2^2 + 1^2	dp[5 - 2^2] + 1 = dp[1] + 1	2
dp[6]	2^2 + 1^2 + 1^2	dp[6 - 2^2] + 1 = dp[2] + 1	3
...
dp[14]	3^2 + 2^2 + 1^2	dp[14 - 3^2] + 1 = dp[5] + 1	3
dp[15]	3^2 + 2^2 + 1^2 + 1^2
dp[16]	4^2	dp[16 - 4^2] + 1 = dp[0] + 1	1
...
dp[32]	4^2 + 4^2	dp[32 - 4^2] + 1 = dp[16] + 1	2

위의 예시를 바탕으로 i 가 n 이고, j * j 가 i 보다 작은 범위 내에서

제곱수의 개수를 구하는 점화식은 dp[i] = Math.min(dp[i], dp[i - j * j] + 1) 이며,

 

n 의 제곱수 개수의 갱신된 최솟값을 정답으로 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];

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

        bw.write(dp[n] + "\n");
        bw.flush();
    }

}