[BaekJoon] 11066번 파일 합치기 (Java) 문제 풀이 [Gold 3]

문제

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

11066번: 파일 합치기

 

어떻게 풀 것인가?

문제를 읽으면서 방향성 자체는 DP로 잡았다.

 

DP에서 중요한 것은 점화식이다. 그래서 우선적으로 그냥 바텀업 방식과 메모제이션으로 문제를 풀었다.

 

메모이제이션 (Memoization) 이란?

• DP를 구현하는 방법 중 한 종류이다.
• 한 번 구한 결과를 메모리 공간에 메모해두고 --> 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법이다. (값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.)

다만, 시간복잡도에 대한 고민이 많았다. 우선 문제에서 주어진 TestCase에 대한 제한이 없었다. 문제에서 주어진 시간제한 2초였기에, 가늠을 할 수 가 없었다.

 

그래서 우선적으로는 그 생각은 뒤로 하고 문제에 대해서 점화식을 분석했다.

 

dp[N+1][N+1] 은 우선적으로 i번 페이지부터 j번 페이지까지 페이지를 합한 최솟값이라 정의하였다. 우리가 원하는 것은 최솟값이다.

 

그리고 아래와 같은 코드로 메모제이션을 완료했다.

private static void DP() {
    for (int i = 1; i <= N; i++) {
        for (int from = 1; from + i <= N; from++) {
            int to = from + i;
            dp[from][to] = Integer.MAX_VALUE;
            for (int divide = from; divide < to; divide++) {
                dp[from][to] = Math.min(dp[from][to], dp[from][divide] + dp[divide + 1][to] + sum[to] - sum[from - 1]);
            }
        }
    }
    sb.append(dp[1][N]).append("\n");
}

3중 포문으로 설명을 하자면

 

첫번째 포문에서는 1 ~ N까지 몇장을 묶을 것인가에 대한 것이고

 

두번째 포문에서는 1부터 k까지 어디부터 묶기 시작할 것 인가에 대한것이다.

 

마지막, 세번째 포문에서는 1부터 k까지 범위가 주어졌을때 특정 지점으로 나눠서 최대값 구하는 것이다.

 

삼중 포문이라서 당연하게 시간복잡도가 초과가 나올 것이라고 생각했으나, 다행히 문제 정답이였다...

 

풀면서 놓쳤던점

시간복잡도에 대한 생각이 많았다. 하지만 문제가 풀려버려서 생각의 깊이가 더욱 들어가지 못했던 것 같다. 시간이 된다면 시간복잡도를 다시 계산해봐야할 것 같다.

 

이 문제를 통해 얻어갈 것

DP에 대한 활용

 

내 코드 

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

// 백준알고리즘 11066번 파일 합치기
public class Main {

    static int N;
    static int[] arr;
    static int[][] dp;
    static StringBuilder sb;
    static int[] sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine());
        sb = new StringBuilder();
        for (int t = 0; t < test; t++) {
            N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr = new int[N + 1];
            sum = new int[N + 1];
            dp = new int[N + 1][N + 1];
            for (int i = 1; i <= N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
                sum[i] = sum[i - 1] + arr[i];
            }
            DP();

        }
        System.out.println(sb);
    }

    private static void DP() {
        for (int i = 1; i <= N; i++) {
            for (int from = 1; from + i <= N; from++) {
                int to = from + i;
                dp[from][to] = Integer.MAX_VALUE;
                for (int divide = from; divide < to; divide++) {
                    dp[from][to] = Math.min(dp[from][to], dp[from][divide] + dp[divide + 1][to] + sum[to] - sum[from - 1]);
                }
            }
        }
        sb.append(dp[1][N]).append("\n");
    }
}

 

참고

X