#25 동적 계획법(Dynamic Programming) 2 - 심화(1)

 지난번 동적 계획법 1에서도 언급했듯이 동적 계획법은 특정 문제를 풀기위한 알고리즘이 아닌 문제를 효율적으로 풀기 위한 방법론이기 때문에 그 난이도가 문제마다 천차만별이며 적용하는 방법 또한 굉장히 다양하다.  그렇기에 문제에 따라서는 동적 계획법 문제임을 알고도 해법을 찾지 못하는 경우도 많다.  이번에는 동적 계획법을 사용하여 해결 가능한 조금 더 어려운 문제들을 풀어본다.

 

 

1. 파일 합치기(https://www.acmicpc.net/problem/11066)

 소설을 구성하는 파일의 크기가 챕터 순으로 주어지고 두 파일을 합쳐 하나의 파일로 만드는 작업의 비용이 두 파일의 크기의 합이라고 할 때, 챕터 순서를 유지하면서 파일을 모두 합치기 위해 필요한 최소비용을 구하는 문제이다. 단순히 가장 작은 두 페이지를 합쳐나가는 방식이라면 heap을 사용하여 간단하게 구현할 수 있지만, 이 문제의 경우 챕터의 순서를 유지해야하나는 조건이 있기 때문에 인접한 두 파일만을 합칠 수 있다.  이 문제는 동적 계획법으로 접근해야한다.

 

 일반적으로 문제해결에 동적 계획법을 적용할 때, 가장 중요한 것은 점화식을 찾는 것이다. i번부터 j번까지의 파일을 하나로 합친 값을 dp[i][n] 이라고 하자.  파일은 두 개씩만 합칠 수 있기 때문에, dp[i][j]은 i번부터 k번까지의 파일, k+1번부터 j번까지의 파일을 각각 합친 두 파일을 합친 경우 중 최솟값에 두 파일의 크기를 합친 값, 즉 i번부터 j번 까지의 파일 크기의 합을 더한 것과 같다고 생각할 수 있다. 

 

예를들어 1번부터 5번 파일까지의 크기가 주어졌을 때, dp[1][5] 를 구하는 경우의 수는 다음 그림과 같다.

k = 1

k = 2

k

k = 4

 위 네 가지 경우 중 최솟값이 1번부터 5번까지의 파일을 합치는 데 드는 최소비용이 된다. 이 점화식을 Python 코드로 표현하면 다음과 같다.

dp[i][j] = min([dp[i][k] + dp[k+1][j] for k in range(i, j)]) + sum(filesize[i:j+1])

 

점화식을 찾아냈으면 나머지는 간단하다.  dp 배열의 초기값을 설정한 뒤 반복문으로 나머지를 채워나가면 답을 찾을 수 있다. 이를 구현한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol11066():
    # 각 케이스의 답변을 저장할 리스트
    answer = []
    for T in range(int(input())):
        # 파일 갯수
        K = int(input())

        # 파일 크기 리스트
        filesize = list(map(int, input().split()))

        # dp[i][j] 는 i부터 j 까지의 파일을 합치는데 드는 최소비용
        # dp[i][i] 는 파일 갯수가 한 개이기 떄문에 합치는 비용 0 - 초기화 별도로 필요없음
        dp = [[0] * K for _ in range(K)]

        # acc[i] 는 인덱스 i 까지의 파일 크기의 합
        # i부터 j 까지의 파일 크기의 합을 구할 경우 acc[j] - acc[i-1] 로 구할 수 있음
        # i가 0일 경우를 대비하여 크기를 K+1로 함
        acc = [0] * (K + 1)
        acc[0] = filesize[0]
        for i in range(1, K):
            acc[i] = acc[i - 1] + filesize[i]

        # i와 j의 차
        for margin in range(1, K):
            # 시작점 i
            # i + margin 이 K를 넘지 않아야 하기 때문에 K-margin-1 까지
            for i in range(K - margin):
                # 끝점 j
                j = i + margin

                # i부터 j 까지의 파일을 두 개의 파일까지 합치기 위한 최소비용은 dp[i][m] + dp[m+1][j] 의 최솟값
                # 두 파일을 하나의 파일로 합치기 위해 필요한 비용은 i부터 j 까지의 파일의 크기의 합
                dp[i][j] = min([dp[i][m] + dp[m + 1][j] for m in range(i, j)]) + acc[j] - acc[i - 1]

        # answer 리스트에 정답 저장
        answer.append(dp[0][-1])

    # 출력 형식에 맞춰 정답 리스트 반환
    return '\n'.join(map(str, answer))

위 코드는 O(K^3)의 시간복잡도로 문제를 해결할 수 있다.  이를 추가적으로 최적화하는 특수한 방법도 있지만 아직은 다루지 않는다.  

 

 

 

2. 행렬 곱셈 순서(https://www.acmicpc.net/problem/11049)

 크기가 NxM 인 행렬 A와  MxK 인 행렬 B를 곱하기 위해 필요한 곱셈 연산의 수는 총 NxMxK 번일 때,  행렬 N개의 크기가 곱할 순서대로 주어졌을 때, 곱셈연산 수의 최솟값을 구하는 문제.

 

import sys

input = sys.stdin.readline


def sol11049():
    # 곱할 행렬의 갯수
    n = int(input())
    
    # 행렬의 크기 리스트
    mats = [tuple(map(int, input().split())) for _ in range(n)]
    
    # dp[i][j] 는 i 행렬부터 j 행렬 까지 곱하기 위한 곱셈 연산 수의 최솟값
    dp = [[0]*n for _ in range(n)]
    
    # i와 j의 차
    for margin in range(1, n):
    	# 시작점 i
        for i in range(n-margin):
        	# 끝점 j
            j = i + margin
            
            # 행렬 i 부터 j 까지 곱하는데 필요한 곱셈 연산 수 의 최솟값
            dp[i][j] = min([dp[i][k] + dp[k+1][j] + mats[i][0] * mats[k][1] * mats[j][1] for k in range(i, j)]) 
    
    # 모든 행렬을 곱하는데 필요한 곱셈 연산 수의 최솟값 반환
    return dp[0][-1]

 1번의 파일 합치기와 거의 동일한 방식으로 접근하면 간단하게 해결 가능한 문제이다.