파게로그

[백준 11066번] 파일 합치기 본문

콤퓨타 왕왕기초/PS

[백준 11066번] 파일 합치기

파게 2022. 2. 15. 09:00

문제 링크: 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
Comments