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

📌문제 출처

백준 단계별 문제풀이 - 동적 계획법 2
https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

❓ 문제

❗ 풀이

• 누적합, 동적계획법

📗 풀이 코드

--- python 3는 시간 초과 / pypy3는 통과
import sys
input = sys.stdin.readline
# 누적합 구하는 함수
def prefix(chaps):
    sum_prefix = [0]
    tmp_sum = 0
    for chap in chaps:
        tmp_sum += chap
        sum_prefix.append(tmp_sum)
    return sum_prefix
# dp 함수
def make_dp(a,b):
    dp[a][b] = min([dp[a][a+i] + dp[a+i+1][b] for i in range(b-a)]) + sum_prefix[b]-sum_prefix[a-1]
for _ in range(int(input())):
    k = int(input())
    chaps = list(map(int,input().split()))
    # 누적합 구하기
    sum_prefix = prefix(chaps)
    # dp 채워넣기
    dp = [[0]*(k+1) for _ in range(k+1)]
    for d in range(1,k):
        for i in range(1,k): # (1,2),(1,3),(1,4),(1,3),(2,4),(1,4)로 대각선부터 채워나간다.
            if i+d <= k:
                make_dp(i,i+d)

    print(dp[1][k])

📗 코드 해설

• 챕터를 연속적으로 합치기에 어떤 챕터부터 합치는 것이 최적일지를 고르는 것이 핵심이다.
• 세 장의 챕터가 있다고 치면 아래와 같은 두가지 방법이 있다.
  방법 1 : [1,(2,3)] : (2,3)을 먼저 합치고 1을 합치기
  방법 2 : [(1,2),3] : (1,2)를 먼저 합치고 3을 합치기
• 방법 1: 1장 비용 + 2장 & 3장 합치는 비용 + 2장 & 3장 합쳐진 챕터 비용 = (1장+2장+3장) + 2장 & 3장 합치는 비용
  방법 2: 1장 & 2장 합치는 비용 + 1장 & 2장 합쳐진 챕터 비용 + 3장 비용 = (1장+2장+3장) + 1장 & 2장 합치는 비용
  최적의 방법 = (1장+2장+3장) + min(1장&2장 합치는 비용, 2장&3장 합치는 비용)
  따라서 3 챕터를 합칠 때의 최적의 방법은 2챕터를 합치는 방법에서 최소값을 찾고 거기에 남은 챕터를 더하는 방법.
• 챕터를 합치는데 있어 연속적으로 합쳐지기에 누적합을 만들어놓고 꺼내서 쓰는 것이 개별 연산 진행보다 빠르다.
• 예제 처럼 챕터별 비용이 [40,30,30,50]인 경우를 살펴보자.
  위와 같이 DP표를 만들어볼 수 있다.
  1장을 만들기 위해(1~1장 합치는 비용)이라고 적어둔 것들은 분할을 좀 더 편하게 연산하기 위해 넣어둔 것이다.
• 이후 세 장을 합치는 방법은 (1~3) / (2~4) 두 종류가 있고 각각에는 1&(2~3) / (1~2)&3 과 2&(3~4) / (2~3)&4가 있다.  
  
• 마지막으로 4개의 장을 합치는 방법은 (1~3)&4 / (1~2)&(3~4) / 1&(2~4) 세 종류가 있다. 
  
  이를 표현하면 dp[1][4] = min(dp[1][3] + dp[4][4], dp[1][2] + dp[3][4], dp[1][1] + dp[2][4]) + (1~4까지 누적합)이고
  일반화 시키면 다음과 같은 코드로 나타낼 수 있다.

dp[a][b] = min([dp[a][a+i] + dp[a+i+1][b] for i in range(b-a)]) + sum_prefix[b]-sum_prefix[a-1]

• 이 dp를 [1,2]부터 좌상단에서 우하단으로 채워나가면 차례대로 완성할 수 있다.