[백준_JAVA_알고리즘] 17626 Four Squares #DP

해당 문제는 DP를 이용해서 풀 수 있습니다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        int[] dp = new int[n + 1];

        dp[0] = 0;
        dp[1] = 1;

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

 

dp[0]은 0개의 제곱수가 필요하므로 0으로 초기화, dp[1]은 1^2=1이므로 1개의 제곱수가 필요해 1로 초기화합니다.

 

점화식은 다음과 같습니다.

dp[i] = Math.min(dp[i], dp[i - (j * j)]);

2부터 n까지 각 숫자에 대해 최소 제곱수 개수를 계산합니다.

일단 dp[i]를 dp[i-1]로 초기화합니다.

j는 1부터 시작해서 j*j가 i보다 작거나 같을 때까지 반복합니다.

각 j에 대해서 i - (j * j)의 dp 값과 현재 dp[i]를 비교해 더 작은 값을 선택합니다.

 

DP 문제의 경우 직접 손으로 풀어보고, 최대한 작은 부분으로 나누어 규칙을 찾는 것이 중요한 것 같습니다.

문제의 패턴을 이해하고 비슷한 DP 문제를 많이 풀어보면 될 것 같습니다.

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.

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