백준 11066번 : 파일 합치기 in Python

11066번: 파일 합치기

 

www.acmicpc.net

위 문제는 서로 인접해 있는 파일들을 계속 합쳐 나가면서 발생하는 비용의 최소값을 구하는 문제이다.

처음에는 서로 인접해 있어야 한다는 조건을 모르고 파일들을 minheap에 넣어 최소가 되는 파일들을 두 개씩 꺼내 합치는 방법으로 했으나 비용이 예제의 결과와 달라 당황했었다.
근데 문제를 자세히 읽어보니 서로 인접한 파일들을 합하는 거라 minheap에 넣는 것 자체가 틀린 풀이였다..

그래서 다른 방식으로 문제에 접근해야 하는데, 바로 dynamic programming을 이용한다.

n개의 파일들을 합하는데 드는 최소 비용을 구하는 과정에서 마지막 합, 즉 k개의 파일들과 n-k개들의 파일들을 합하는 과정을 생각해 보자.(k = 1,2,...,n-1) 여기서 어떻게 합하든지 간에 최소 n개의 파일들의 각 비용은 요구될 것이다.

예를 들어, 백준의 예제에서 나오는 예시인 40 30 30 50을 생각해 보자. 최종적으로 두 파일묶음을 합쳐 4개의 파일을 모두 합치는데 드는 최소 비용을 구할 때 나올 수 있는 경우의 수는 다음과 같다.
40 + (30 + 30 + 50)
(40 + 30) + (30 + 50)
(40 + 30 + 30) + 50
이 합은 모두 40 + 30 + 30 + 50, 즉 4개의 파일의 각 비용의 합과 같다. 그러므로 4개의 파일을 합치는데 드는 비용은 항상 4개의 파일들의 각 비용의 합을 포함한다.

여기서 이제 k개의 파일들과 n-k개의 파일들을 합치는 비용까지 합한다면 전체 n개의 파일들을 합치는 비용이 될 것이다. 그런데 우리는 비용의 최소값을 구하고 있으므로 k가 2~n-2일 때까지 k개의 파일들과 n-k개의 파일들을 합치는 최소 비용을 더한 값들을 전부 계산해 그 중에서 최소값을 뽑으면 된다. 여기서 k가 1일 때, n-1일 때에는 하나의 파일을 합치는 경우는 없으므로 n-1개의 파일들을 합치는 최소 비용만 고려한다.

코드는 다음과 같이 구성한다.

1. K * K matrix를 만들고 matrix의 (i, j) 성분은 input으로 받은 array의 i번째 성분부터 j번째 성분까지의 합으로 한다.
2. 최소값을 구하는 게 문제가 되기 시작하는 지점은 array의 길이가 3 이상일 때부터이므로 d(최소값을 구하고자 하는 subarray의 길이)를 3부터 시작해 K까지 점차 늘려가는 for loop을 만든다.
3. for 문 내에서 시작 index i에 대한 for loop을 만드는데, i가 가질 수 있는 값은 0~K-d+1이다.
4. 시작 index, subarray의 길이가 있으니 끝 index j를 구한다.
5. 이제 k가 i+1일 때부터 j-1일 때까지 matrix[i][k] + matrix[k+1][j]들, matrix[i][j-1], 그리고 matrix[i+1][j] 중 최소값을 구한다.
6. 최소값을 matrix[i][j]에 더해준다.
7. 결과값으로 matrix[0][K-1]을 출력한다.

이를 코드로 나타내면 다음과 같다.

T = int(input())
for _ in range(T):
    K = int(input())
    arr = list(map(int, input().split()))
    mat = [[0]*K for _ in range(K)]
    for i in range(K):
        s=0
        for j in range(K):
            if i <= j:
                s+=arr[j]
                mat[i][j] = s
    for d in range(3, K+1):
        for i in range(K-d+1):
            j = i+d-1
            arr2 = [mat[i][k] + mat[k+1][j] for k in range(i+1, j-1)]
            if arr2:
                m = min(arr2)
                mat[i][j] += min(m, mat[i][j-1], mat[i+1][j])
            else:
                mat[i][j] += min(mat[i][j-1], mat[i+1][j])
    print(mat[0][K-1])