[Baekjoon] 파일 합치기(python)

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

문제 접근

DP 문제이다.

 

i~j까지의 파일을 합치는데 드는 최소 비용을 dp배열에 저장하면서 문제를 해결했다.

---

풀이 과정

앞서 말한 것처럼 i~j까지의 파일을 합치는데 드는 최소 비용을 dp배열에 저장하면 된다.

예를 들어, 0~2까지의 파일을 합치는 데 드는 최소 비용은 [0, 1~2]와 [0~1, 2] 중 작은 값이 될 것이다.

 

0~3까지의 파일을 합치는 경우는 [0, 1~3], [0~1, 2~3], [0~2, 3] 중 작은 값이다.

이렇게 최소 비용이 드는 임시 파일의 케이스를 찾고 실제 파일을 합치는데 드는 비용을 더해주면 파일을 합칠 때 드는 최소 비용을 구할 수 있다.

 

1. 임시 파일의 크기 조합을 구한다

for j in range(1, n):
        for i in range(j - 1, -1, -1):

            dp[i][j] = sys.maxsize

            for k in range(i, j):

                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])

2. 파일을 합치는데 드는 비용을 더해준다.

dp[i][j] += files[j] - files[i - 1] if i > 0 else files[j]

---

정답 코드

"""
    백준 11066번 파일 합치기
"""

import sys


T = int(sys.stdin.readline())

for _ in range(T):
    n = int(sys.stdin.readline())

    files = list(map(int, sys.stdin.readline().split()))
    dp = [[0] * n for _ in range(n)]

    # 0 ~ N -1번째 파일까치 합
    for i in range(1, n):
        files[i] += files[i - 1]

    for j in range(1, n):
        for i in range(j - 1, -1, -1):

            dp[i][j] = sys.maxsize

            for k in range(i, j):

                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])

            dp[i][j] += files[j] - files[i - 1] if i > 0 else files[j]

    print(dp[0][-1])