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

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

11066번: 파일 합치기

Problem

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

조건

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

SOL

CMM의 원리를 그대로 따르고 있는 문제이다.즉, 괄호를 어디에 치냐에 따라서, 값이 달라지는 유형의 문제

단, 여기서는 누적합의 형태만 살짝 달라졌을 뿐이다.

DP table을 작성해보면 똑같고, 누적합을 이용해서, 뒤에 식에서 간단하게 표현해줬다.

 

Sum[j+1] - S[i] 인 이유

• 예를들어, A,B,C,D 4개의 파일의 합을 구한다고 생각해보자.
• DP[i][j] = DP[i][k] + DP[K+1][j] + sum(A[i]~A[j]) 이다.
• DP[1][3]  =  BCD의 파일합을 구하는 과정이며, 여기서는 BC,CD 중에 작은 값 + BCD의 합을 구해야한다. 문제에서, 마지막에 합치는 과정도, 파일의 cost로 작용하고 있음!
• 따라서, sum[j+1]-S[i] = A[i] 까지의 누적합을 제외한 , A[j]까지의 누적합을 나타내는 것이다.

 

def solve():
    N, A = int(input()), list(map(int, input().split()))
    # S[i]는 1번부터 i번까지의 누적합
    S = [0]*(N+1)
    S[1]= A[0]
    for i in range(1, N+1):
        S[i] = S[i-1] + A[i-1]

    # DP[i][j] : i에서 j까지 합하는데 필요한 최소 비용
    # DP[i][k] + DP[k+1][j] + sum(A[i]~A[j])
    DP = [[0]*(N) for _ in range(N)]
    for diagonal in range(1,N):
        for i in range(0,N-diagonal):
            j=i+diagonal
            if diagonal ==1:
                DP[i][j] = A[i]+A[j]
                continue
            DP[i][j]=float('inf')
            for k in range(i,j):
                DP[i][j] = min(DP[i][j],DP[i][k]+DP[k+1][j]+S[j+1]-S[i])
    print(DP[0][N-1])

for _ in range(int(input())):
    solve()