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

진짜 어려웠다 이해하려고 3일동안 코드를 보았다

 

---

문제

 

 

코드

def min_merge_cost(files):
    n = len(files)
    dp = [[0] * n for _ in range(n)]  # dp[i][j]: i부터 j까지 파일을 합치는데 필요한 최소 비용

    # 파일의 부분합 미리 계산
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + files[i - 1]

    # 대각선 길이 1부터 n-1까지 순회
    for length in range(1, n):
        for i in range(n - length):
            j = i + length
            dp[i][j] = float('inf')  # 무한대로 초기화

            # 파일을 합치는 모든 경우의 수를 고려하여 최소 비용 계산
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + prefix_sum[j + 1] - prefix_sum[i]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

# 테스트 케이스 수 입력
t = int(input().strip())

# 각 테스트 케이스에 대해
for _ in range(t):
    # 장의 수 입력
    k = int(input().strip())
    # 파일 크기 입력
    files = list(map(int, input().split()))

 

 

설명

머리 터지는줄 알았다

여러 블로그를 봐도 이해가 안되는 것 투성이였다ㅠ

나처럼 초보자분들은 이 글을 보고 시간을 단축했으면 좋겠다!

 

prefix_sum의 부분은 백준의 동적계획법 1에 등장하는 기초 알고리즘인데 포스팅 하게 되면 링크를 첨부하겠습니다.

 

핵심 알고리즘은 파일을 합치기 위해 경우의 수를 나눠야 하는데 그게 3번째 for문인 for k in range(i, j)에서 이루어집니다.

 

dp[i][j]를 보면 대각선으로 값을 채우는데 그 이유는 부분 문제로 해결하기 위해서 입니다.

• DP 테이블을 채우는 순서는 부분 문제를 해결하는 순서와 밀접한 관련이 있습니다.
• 부분 문제를 해결할 때, 더 작은 부분 문제를 먼저 해결하고 이를 이용해 더 큰 부분 문제를 해결해야 합니다.
• dp[i][j]를 계산하려면 dp[i][k]와 dp[k+1][j]가 필요합니다. 여기서 i <= k < j 이므로 dp[i][k]와 dp[k+1][j]는 dp[i][j]보다 먼저 계산되어야 합니다.
• 따라서, 파일 길이 1부터 n-1까지 순차적으로 채우는 것입니다. 이 과정은 대각선으로 테이블을 채우는 것과 같은 순서가 됩니다.

 

예시

dp[0][1] = min(dp[0][0] + dp[1][1] + (prefix_sum[2] - prefix_sum[0])) = 70
dp[1][2] = min(dp[1][1] + dp[2][2] + (prefix_sum[3] - prefix_sum[1])) = 60
dp[2][3] = min(dp[2][2] + dp[3][3] + (prefix_sum[4] - prefix_sum[2])) = 80

dp[0][2] = min(dp[0][0] + dp[1][2] + (prefix_sum[3] - prefix_sum[0]), dp[0][1] + dp[2][2] + (prefix_sum[3] - prefix_sum[0])) = 170
dp[1][3] = min(dp[1][1] + dp[2][3] + (prefix_sum[4] - prefix_sum[1]), dp[1][2] + dp[3][3] + (prefix_sum[4] - prefix_sum[1])) = 160

dp[0][3] = min(dp[0][0] + dp[1][3] + (prefix_sum[4] - prefix_sum[0]), dp[0][1] + dp[2][3] + (prefix_sum[4] - prefix_sum[0]), dp[0][2] + dp[3][3] + (prefix_sum[4] - prefix_sum[0])) = 300

 

 

저도 문제를 푸는데 오래 걸렸습니다 초보자 분들 다같이 화이팅!!