악곱 == 악성곱슬

DP

---

개인적으로 동적 프로그래밍은 점화식을 세우는게 제일 중요하고 어려운 것 같다.

처음에 이 문제는 “연속적” 이라는 말을 보지 못하고 그리디, 우선순위 큐를 이용하여 해결할 수 있을 줄 알았다.

하지만 순서를 지켜야 하는 문제이므로 동적 프로그래밍 문제임을 깨달을 수 있었다.

우선 점화식을 세우기 위해서는 부분 문제로 어떻게 나눌 수 있을지를 고민해야 한다. 1~N 까지를 해결해야 하는 솔루션으로 본다면 이를 i~j까지로 트리 구조로 나누면서 다음과 같이 생각해봐야 한다.

어느 두 파일을 더해야 최소 비용이 나올지 모르기 때문에 다음과 같이 계산해야한다. 여기서 sub problem에서 연산한 비용을 더하면서 올라와야 하기 때문에 파일의 비용의 부분합을 더하여 점화식을 완성한다.

f(i, j) = min( f(i, mid) + f(mid + 1, j) + acc(i ~ j) )

이 문제는 점화식을 세워도 코드로 옮기기도 꽤 어렵다는 문제가 있다. 점화식 대로 코드를 구현하려면 다음과 같이 부분합의 길이를 offset으로 두고 대각선으로 탐색하는 방향으로 구현해야 한다.

i 는 대각선을 반복하는 iteration 을 의미하고 offset은 i로부터 대각선으로 얼만큼 떨어져 있는지를 의미한다. 즉 부분합의 길이이다. 그리고 mid는 0~부분합의 길이로 중간에 부분합을 자르는 token 역할을 한다.

이를 염두해서 구현한 코드는 아래와 같다.

구현

---

import sys

def dp(k):
    # 초기 설정
    table = [[0]*(k+1) for _ in range(k+1)]
    acc = [0] * (k+1)
    for i in range(1, k+1):
        acc[i] = acc[i-1] + files[i-1]

    for offset in range(1, k+1):
        for i in range(1, k - offset + 1):
            x, y = i, i+offset
            table[x][y] = INF
            for mid in range(offset):
                table[x][y] = min(table[x][y], (table[x][x+mid] + table[x+1+mid][y] + acc[y] - acc[x-1]))
    return table[1][k]

if __name__ == "__main__":
    T = int(sys.stdin.readline().rstrip())
    INF = int(1e9)
    for _ in range(T):
        K = int(sys.stdin.readline().rstrip())
        files = list(map(int, sys.stdin.readline().rstrip().split()))
        print(dp(K))