백준 11066 파일 합치기 - DP

풀이

시간을 정말 많이 써서 고민했던 문제이다. 결국 풀이를 보고 해답을 얻었다 ㅠㅜ..

풀기 위해 고민해야 할 부분을 정리해보자.

DP 변수 설정

이렇게 기본 소스가 되는 novel 변수를 합쳐서 하나의 파일을 만드는 문제는 idx가 줄어드므로 시작위치, 끝 위치를 DP 변수로 설정하면 된다.

즉, DP[start][end] = start~end idx까지의 파일합치기 비용

점화식 찾기

DP 변수를 설정했으면 실제 변수 대입을 통해 규칙을 찾고 그 규칙으로 부터 점화식을 세우자.

DP를 사용하기 위해서는 합치는 길이가 작은 것 부터 점점 키워가면 된다.

len==1

• dp[i][i] = 0

len==2

• dp[i][i+1] = arr[i] + arr[i+1] + dp[i][i] + dp[i+1][i+1]
• 두 개의 페이지를 합칠땐, 기존 합치기 비용 + 추가 비용을 생각하면 된다.
• 기존 합치기 비용 : dp[i][i] + dp[i+1][i+1]
• 추가 비용 : i ~ i+1 까지의 부분합

len ==3

• 길이가 2보다 커지면 경우의 수가 늘어난다.
• 40 30 30 을 합치는 비용은 40 / 30 30 으로 합치거나 40 30 / 30 으로 합치게 된다.
• 최솟값을 구하므로 두개를 모두 계산한 후 최솟값으로 설정하자.
• dp[i][i+2] = dp[i][i+1] + dp[i+2][i+2] + 부분합
• OR
• dp[i][i+2] = dp[i][i] + dp[i+1][i+2] + 부분합

파일을 합치는 비용은 각 인덱스의 값을 모두 합친 부분합임을 포인트로 찾아야 한다.

len==len

• dp[start][end] = dp[start][stop] + dp[stop+1][end] + sum[end+1] - sum[start]

최종 코드

import java.util.*;

public class Main {


    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int T = Integer.parseInt(sc.nextLine());

        for (int t = 0; t < T; t++) {

            int n = Integer.parseInt(sc.nextLine());

            String[] inp = sc.nextLine().split(" ");

            ArrayList<Integer> arr = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                arr.add(Integer.parseInt(inp[i]));
            }

            int[][] dp = new int[n + 1][n + 1]; // 정답 = dp[0][n-1]

            int[] sum = new int[n+1];

            for (int i = 1; i < n+1; i++) {
                sum[i] = sum[i-1]+ arr.get(i-1);
            }

            for (int len = 2; len <= n; len++) {

                for(int start = 0;start < n;start++){
                    int end = start+len-1;
                    if(end >= n){
                        continue;
                    }
                    dp[start][end] = Integer.MAX_VALUE;

                    // stop 지점은 앞에 포함됨, stop < end
                    for(int stop = start; stop <end ; stop++){
                        dp[start][end] = Math.min(
                                dp[start][end],
                                dp[start][stop] + dp[stop+1][end] + sum[end+1] - sum[start]
                        );
                    }
                }
            }
            System.out.println(dp[0][n-1]);
        }
    }

}