[🥇3 / 백준 11066 / 파이썬] 파일 합치기

 

11066번: 파일 합치기

문제

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.

소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.

입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

 

예제 입력  2 4 40 30 30 50 15 1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

예제 출력  300 864

 

풀이

 

주어진 페이지들을 최소 비용으로 합치는 문제이다.

 

문제의 규칙에 따라 페이지를 합쳤을 때, 최소한의 비용을 만들 수 있는 규칙 같은 것은 딱히 있진 않았다.

당연하지만 결국 다이나믹 프로그래밍으로 점화식을 만들어서 풀어야 한다.

 

우선 40 30 30 50을 보자.

 

그리고 40 30 30 50을 합치는 방법을 분할해 보자.

 

우선, (40) (30 30 50) 꼴로 나눌 수 있을 것이다.

여기서 다시 30 30 50도 아직 크므로 분할이 된다.

그렇다면 ((30 30) 50), (30 (30 50)) 두 가지 방법으로 나눌 수 있다.

즉, 재귀의 가능성이 있다는 것이다.

여기서 둘 중 더 최소한의 비용이 나오는 것을 구한 뒤 이를 메모이제이션으로 기록하여 나가면 된다.

 

import sys
input = sys.stdin.readline

def dp(start,end):
		# 메모이제이션이 된 구간
        if d[start][end] != -1:
            return d[start][end]
        
        if start == end:
            return 0
        
        ans = float('inf')
        s = sum(f[start:end+1])
        for i in range(start, end):
        	# 양분할 한 것 각각 + 둘을 합친 것
            temp = dp(start,i) + dp(i+1,end) + s
            
            if ans > temp:
                ans = temp
            
            d[start][end] = ans
        return ans

for i in range(int(input())):
    n = int(input())
    f = list(map(int,input().split()))
    d = [[-1]*(n+1) for i in range(n+1)]
    
    print(dp(0,n-1))

 

위 코드는 약 O(n^3)의 시간복잡도를 가지고 있다.

이와 유사하게 구성한다면 c++ 등의 언어로는 풀리는 것 같다.

하지만 안타깝게도 파이썬은 무거운 언어이다 보니 시간초과에 걸린다.

 

이것저것 검색해보니 이 문제를 풀 때 크누스 최적화를 통해

O(n^3)의 시간복잡도를 약 O(n^2)까지 줄일 수 있다고 한다.

 

https://suri78.tistory.com/15

 

위 블로그를 참고하여 코드를 작성해서 통과는 하였다.

이번엔 다른 사람의 코드로 통과한 셈이지만 다음 번엔 혼자 힘으로 꼭 풀어보겠다.

 

import sys
input = sys.stdin.readline

for i in range(int(input())):
    n = int(input())
    f = list(map(int,input().split()))
    d = [[0]*(n+1) for i in range(n+1)]
    
    for i in range(n-1):
        d[i][i+1] = f[i] + f[i+1]
        for j in range(i+2,n):
            d[i][j] = d[i][j-1] + f[j]

    for v in range(2,n):
        for i in range(n-v):
            j = i+v
            d[i][j] += min([d[i][k] + d[k+1][j] for k in range(i,j)])
    
    print(d[0][n-1])