[백준알고리즘] 11066번: 파일 합치기 -Python

[백준알고리즘] 11066번: 파일 합치기 -Python

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

11066번: 파일 합치기

추가) 새로 풀어봤다. 밑에 나오는 크누스 최적화를 사용 안 하고 그냥 해봤다. 크누스 최적화가 이해되지 않더라도 그냥 DP라 생각하고 풀면 될 것 같다. 이렇게 풀고 나니 다들 이렇게 풀었다. 이렇게 푼 방법이 크누스 최적화가 맞는 건지 생각까지는 안 하려고 한다. 사실 보면 같은 코드이기는 한데 설명이 조금 다르다. 아래쪽에 추가해놓겠다.

 

이렇게 해도 PyPy로만 통과되는데.. Python으로 통과한 코드와 별 차이가 없는 것 같은데... 반복문 횟수를 통일시켜서 줄여봐도 안된당 ㅎㅎ;

---

이거 푸는데 엄청 오래 걸렸다.. 더 열심히 해야겠다...

처음에 풀 때는 풀이방법부터 잘못 정하고 있어서 고생했다.

 

일단 풀이방법을 연쇄 행렬 곱셈처럼 해보면 될 것 같다고 알아차리기도 오래 걸렸다. 알아차린 후 처음에는 풀이를 잘 못 접근했었다.

40 30 30 을 예로 들면, 우리는 여기서 (70 + 100)과 (60 + 100)을 비교해야 하는데, (70 + (70 + 30))과 (60 + (60 + 40))으로 계산을 하려 하니 복잡했었다. 간단히 70과 60만 비교한 후 40+30+30을 추가해주면 되는 방법이 더 쉬운데 말이다. 좀 더 다양하게 보도록 노력해야겠다.

 

게다가 코드를 작성할 때는 i번째부터 j번째 파일까지 연속으로 더해놓은 이중 리스트와 i번째부터 j번째 파일까지 합들의 합의 최소를 저장하는 것까지 두 가지를 만들어서 재귀 함수를 만들어 사용했다. 그런데 시간 초과가 계속 떠서 방향을 바꿔서 재귀는 사용 안 하고 Bottom up으로 채워나가기로 결정했다.

 

그래서 찾다 보니 Knuth Optimization이라는 것이 있었다. (이것을 이용한 설명은 링크로 들어가면 해놓았다.)

해당 개념을 적용해서 겨우겨우 PyPy로 통과할 수 있었다..

import sys

T = int(sys.stdin.readline())
K = []
file = []

for t in range(T):
    K.append(int(sys.stdin.readline()))
    file.append(list(map(int, sys.stdin.readline().split())))

for t in range(T):
    k = K[t]
    f = file[t]

    sum = [f[0]]
    for i in f[1:]:
        sum.append(i + sum[-1])
    accumulated = [[0] * k for _ in range(k)]

    accumulated[0][1] = sum[1]
    for i in range(1, k - 1):
        accumulated[i][i + 1] = sum[i + 1] - sum[i - 1]
    
    for gap in range(2, k):
        for i in range(k - gap):
            accumulated[i][i + gap] = float('inf')

            for j in range(i, i + gap):
                accumulated[i][i + gap] = min(accumulated[i][i + gap],
                                              accumulated[i][j] + accumulated[j + 1][i + gap])

            accumulated[i][i + gap] = accumulated[i][i + gap] + sum[i + gap] - sum[i - 1]\
                                      if i > 0 else accumulated[0][gap] + sum[gap]

    print(accumulated[0][k - 1])

sum은 f[0]부터 f[i]까지 연속으로 더한 값으로 f[i] - f[j - 1] (j <= i)을 하게 되면 f[j]부터 f[i]까지의 연속합을 구할 수 있다.

accumulated는 누적합을 갖는 이중리스트로, Knuth Optimization의 점화식에 맞게 작성을 했다.

gap은 구하려는 accumulated[a][b]에서 a와 b의 간격이며, 어차피 파일의 수는 3개 이상이기 때문에 2칸 이상 떨어져 있을 때부터 시작한다. diagonal순서대로 채우기 위해서 다음과 같은 3중 for문을 사용했다.

 

이 한문제로 이렇게 시간을 많이 잡아먹다니.. 더 열심히 하자!

 

---

 

2020.03.02 새롭게 푼 방법이다. 크누스 최적화 같은 어려운 소리를 치우고 그냥 어떻게 풀었는지 설명해보도록 하겠다.

 

우선 table이라는 이중 리스트를 통해서 합을 구해주었다. 이때 아래의 코드를 보면 결국에 table[i][j]는 다음과 같은 식을 만족하게 된다.

table[i][j] = table[i][j-1] + page[j] + min(minimum)

 

 

간단하게 table[0][2]를 살펴보겠다. table[0][2]는 0부터 2까지 더해서 나타날 수 있는 최솟값이 된다. 마찬가지로 table[1][3]은 1부터 3까지 더해서 나타날 수 있는 최솟값이 된다. 이 최솟값이 되는 부분은 min에서 결정되게 되는데, 최솟값을 더해주기 전에 table[i][j-1] + page[i]가 되는 이유를 살펴보도록 하겠다.

 

table[0][2]의 경우에는 두 가지 경우가 존재한다.

 

1. (page[0] + page[1]) + page[2]

2. page[0] + (page[1] + page[2])

 

 

각각 계산되는 비용은 다음과 같다.

 

(page[0] + page[1]) + page[2]

: (40 + 30) + (70 + 30) # 첫 번째 합의 비용 40+30 = 70, 이후 두 번째 합의 비용 70+30 = 100

page[0] + (page[1] + page[2])

: (30 + 30) + (60 + 40) # 첫 번째 합의 비용 30+30 = 6-, 이후 두 번째 합의 비용 60+40 = 100

 

보다시피 첫 번째 합의 비용은 다르지만 두 번째 합의 비용은 100으로 같다. 그 이유는 결국에 마지막 합의 비용은 0부터 2까지의 모든 수를 더한 값과 같기 때문이다.

 

 

따라서 최솟값을 결정해주는 것은 마지막 합의 비용이 아닌 그 이전의 비용이다. 그 부분이 min(minimum)을 통해서 구할 수 있도록 해주었다. minimum에는 (table[i][k] + table[k+1][j]) 의 값들이 들어가게 된다. 이 값들이 의미하는 것은 ((i~k까지 더한 비용의 최솟값) + (k+1~j까지 더한 비용의 최솟값))이고, subproblem 으로 나눠서 생각할 수 있게 되었으니 DP로 충분히 해결할 수 있는 문제가 되었다.

 

결국 dp를 이용해 대각선 방향으로 채워주는 방식으로 전체의 최소 비용을 구할 수 있게 된다.

 

import sys
input = sys.stdin.readline

t = int(input())
for __ in range(t):
    k = int(input())
    page = list(map(int, input().split()))
    
    table = [[0]*k for _ in range(k) ]
    for i in range(k-1):
        table[i][i+1] = page[i] + page[i+1]
        for j in range(i+2, k):
            table[i][j] = table[i][j-1] + page[j]

    for d in range(2, k): # diagonal
        for i in range(k-d):
            j = i+d
            minimum = [table[i][k] + table[k+1][j] for k in range(i, j)]
            table[i][j] += min(minimum)

    print(table[0][k-1])

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다