파게로그
[백준 11066번] 파일 합치기 본문
문제 링크: 11066번 파일 합치기
https://www.acmicpc.net/problem/11066
일단 DP문제라고 하는데 왜 DP인지부터 생각해보자. 그다지 바람직하지는 않지만, 우리가 적절한 알고리즘을 고르는 데에 사용할 수 있는 판단 근거 중 하나는 주어지는 값의 범위이다. 이 문제에서는 소설을 구성하는 장의 수 K가 500 이하로서 스위핑으로 해결되기는 힘들며, O(n^2)이라고 하기에도 약간 작은 숫자이므로 O(n^3) 정도를 생각해봐야 한다는 것을 알 수 있다. 또한 "여러 장들이 연속이 되도록 파일을 합쳐나가"라는 부분에서 인접한 파일만 합쳐야 한다는 것을 알 수 있는데, 따라서 정렬이나 투 포인터 등 처리 순서가 자유로울 때에 사용할 수 있는 기법들도 여기서는 모두 후보군에서 제외해야 한다.
그래서, 다시 왜 DP인가?
아래 예시에 대해서, 파일을 합치는 여러가지 방법이 있겠지만 아래 두 가지만 생각해보자.
[100, 30, 50, 200, 60]
[100, 30, 50, 200, 60]
[130, 50, 200, 60] cost: 130
[180, 200, 60] cost: 180
[180, 260] cost: 260
[440] cost: 440
[100, 30, 50, 200, 60]
[100, 80, 200, 60] cost: 80
[180, 200, 60] cost: 180
[180, 260] cost: 260
[440] cost: 440
[180, 200, 60] 이후의 과정들은 우리가 똑같은 과정을 반복하고 있음을 알 수 있다. 잘 생각해보면, 파일을 합치는 순서에 따라 비용에는 차이가 발생하지만, 파일을 합친 결과물의 크기는 동일하기 때문에, 파일을 합쳤을 때 크기만 같다면 그 이후 과정에서는, 순서가 같은 한, 비용도 동일하게 발생한다.
이러한 반복 과정, 즉 중복된 부분 문제를 한 번만 계산하고자 하는 목적에서 memoization을 이용할 수 있는 것이다.
이제 DP를 사용해야 하는 것까지는 알았다. 여기서부터는 연습의 영역이라고 생각하는데, 이 문제에서는 D(i, j)를 i번째 파일부터 j번째 파일까지 합치는 데에 필요한 최소 비용이라고 정의할 수 있다. 점화식은 다음과 같다.
D(i, j) =
0 if i=j
A(i) + A(j) if j=i+1
min(D(i, i)+D(i+1, j), D(i, i+1)+D(i+2, j), ..., D(i, j-1)+D(j, j)) + (A[i] + A[i+1] ... + A[j]) else
마지막 줄에서 A[i] + A[i+1] + ... + A[j]는 왜 있을까? 이런 문제를 풀면 항상 헷갈리는 부분이 되기도 한다. D(i, j)는 i번째 파일부터 j번째 파일까지 합치는 데에 필요한 최소 비용이라고 했다. [30, 50, 100]이라는 예시에서, 1번째 파일과 2번째 파일을 먼저 합치든, 2번째 파일과 3번째 파일을 먼저 합치든, 어느 경우에든 최종적으로는 180의 비용이 마지막 단계에서 발생한다. 그렇다면 min()의 정체는? 그 이전 단계, 즉 30+50 또는 50+100의 비용이다.
한편, 여기서 Knuth's Optimization이라는 것을 적용해서 O(n3)을 O(n2)으로 줄일 수 있다고 한다. 하지만 코딩테스트에서 나올 범위는 아니라고 하니 접어두도록 한다. 코딩테스트를 준비하는 입장에서, 이 문제에서 최적화할 수 있는 부분은 A[i] + A[i+1] + ... + A[j]를 누적합을 통해 빠르게 구할 수 있도록 해두는 것 정도이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int k;
static int[] files;
static int[] pre;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int test = Integer.parseInt(br.readLine());
while (test-- > 0) {
k = Integer.parseInt(br.readLine());
files = new int[k + 1];
pre = new int[k + 1];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= k; i++) {
pre[i] = files[i] = Integer.parseInt(st.nextToken());
}
for (int i = 2; i <= k; i++) {
pre[i] += pre[i - 1];
}
dp = new int[k + 1][k + 1];
for (int i = 0; i < k + 1; i++) for (int j = 0; j < k + 1; j++) dp[i][j] = -1;
for (int i = 1; i <= k; i++) {
for (int j = i + 1; j <= k; j++) {
dp[i][j] = get(i, j);
}
}
sb.append(dp[1][k]).append('\n');
}
System.out.print(sb);
}
static int get(int s, int e) {
if (s >= e) {
return 0;
}
if (e == s + 1) {
return files[s] + files[e];
}
if (dp[s][e] != -1) {
return dp[s][e];
}
int min = Integer.MAX_VALUE;
for (int i = s; i <= e - 1; i++) {
int sum = get(s, i) + get(i + 1, e);
if (sum < min) {
min = sum;
}
}
return dp[s][e] = min + pre[e] - pre[s - 1];
}
}
'콤퓨타 왕왕기초 > PS' 카테고리의 다른 글
[백준 1188번] 음식 평론가 (0) | 2022.03.15 |
---|---|
[백준 1912, 1749번] 연속합, 점수따먹기 (0) | 2022.02.27 |
[백준 10775번] 공항 (0) | 2022.02.13 |
binary search and parametric search (1) | 2022.02.06 |
[백준 1005번] ACM Craft (0) | 2021.11.29 |