문제
분석
두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 하나의 파일로 합칠 때 필요한 최소비용을 구하는 문제이다.
백준 - 13975번: 파일 합치기3과 비슷해 보이나, 문제에서 "연속적인"이라는 말 때문에 인접한 파일을 합쳐야 한다는 점이 다르다.
어떤 i파일부터 j파일까지 일렬로 있다고 할 때, 그 사이 파일을 k라고 칭하자.
i부터 k까지 합친 결과와 k+1부터 j까지 합친 결과를 안다고 할 때 그 둘을 더한다.
k는 여러가지 경우가 있으므로 그 중 가장 작은 값을 택하면 된다.
이를 코드로 나타내면 dp[i][j]는 i부터 j까지 하나로 합치는데 드는 최소 비용이고,
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])가 된다.
그런데 합칠 때마다 값이 누적된다. 따라서 미리 누적합을 구해놓고 해당 범위의 모든 값을 더한 부분합을 더해줘야 하기 때문에 정확히는 이렇게 고쳐야한다.
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+prefix[j]-prefix[i-1])
(필자는 누적합 구할 때 0을 앞에 넣어 편리하게 계산한 것 때문에
prefix[j+1]-prefix[i]로 코딩했다.)
dp배열을 채울 때 대각선 상단만 채우고, 아래와 같은 순서로 채워진다.
i와 j가 같은 경우는 같은 파일을 가리키므로 합치는 비용이 없다. 따라서 0으로 초기화한다.
코드
해결언어 : Python
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
n = int(input())
arr = list(map(int, input().split()))
prefix = [0]*(n+1)
for i in range(1, n+1):
prefix[i] = prefix[i-1]+arr[i-1]
INF = sys.maxsize
dp = [[INF]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 0
for cnt in range(n-1):
for i in range(n-1-cnt):
j = i+cnt+1
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+prefix[j+1]-prefix[i])
print(dp[0][n-1])
해당 코드는 pypy3로 통과됐다.
끝으로..
dp의 문제 유형도 매우 다양한 것 같다. 많이 접해보고 연습 해봐야겠다.
