[백준] 11066번 : 파일 합치기

11066번: 파일 합치기

11066번: 파일 합치기

📄 문제개요

• 두개의 파일을 합칠때 필요한 비용이 주어질때, 한개의 파일을 완성하는데 필요한 비용의 총 합을 계산하여라.
• 최소비용으로 계산하는 프로그램을 작성하여라.
• 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고 라는 조건으로 우선순위 큐로 풀 수 없다.

🤔 문제분석

우선순위 큐

• 해당문제는 우선순위 큐로 문제를 해결 할 수 있습니다. 최소비용을 갖으려면 항상 작은값을 합쳐야합니다.
• 따라서 우선순위큐로 항상 작은값 2개를 선택하여 더해서 파일을 하나로 만듭니다.

다이나믹 프로그래밍

• 현재파일에서 이전의 파일의 합친값과 다음파일의 합친값중 최솟값을 찾아낸다.
• 파일 C1, C2, C3가 있을때, (C1+C2) + C3와, C1 + (C2+C3) , 당장 더한값과 당장 더하지 않은값중 최소값을 갱신한다.
• dfs(i, total)을 함수로 둔다.
• min(dfs(2, C1+C2) + C3, dfs(2, C2+C3) + C1)

📝 의사코드

우선순위 큐 ( 해당문제로는 풀 수 없음 조건 불가 )

• 주어진 파일의 크기를 오름차순으로 정렬한다.
• 그리고 모든값을 우선순위큐에 넣는다.

1. 큐에서 2개의 가장 작은 값을 뺀다.
2. 2개를 더해서 큐에 다시 넣는다.
3. 큐가 1개가 될때까지 1, 2를 계속 반복한다.

다이나믹 프로그래밍

• 구간합 문제로 접근하자.
• dp[0][2]는 0번파일부터 2번파일까지의 최소값이 저장될 테이블이다.
• dp[0][0] = 0 이고, dp[0][1]은 0번파일부터 1번파일까지의 합이다.
• dp[0][2] = dp[0][0] + dp[1][2], dp[0][1] + dp[2][2]중 최소값이다.

💻 코드

import sys
input = sys.stdin.readline

def prefix_sum(p_sum, start, end):
    return p_sum[start] - p_sum[end]

def solve():
    N = int(input())
    file = list(map(int, input().split()))
    p_sum = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        p_sum[i] = p_sum[i-1] + file[i-1]
    
    dp = [[int(1e9) for _ in range(N)] for _ in range(N)] # (i, j) 까지의 최소 합
    
    for i in range(N):
        dp[i][i] = 0
        
    for s in range(2, N+1):
        for start in range(N-s + 1):
            end = start + s - 1
                
            for mid in range(start, end):
                dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid+1][end] + prefix_sum(p_sum, end+1, start))

    #print(dp)
    print(dp[0][N-1])
T = int(input())
for _ in range(T):
    solve()

🎯 피드백 및 개선사항

• 문제를 해결하는 방법을 떠올리기는 쉬웠으나 , 막상 점화식을 세우려고하니 어렵게 느껴졌습니다.
• 문제의 핵심은 구간합을 이용하여 최소값을 구하는 문제 였습니다.

❓다른사람은 어떻게 풀었을까?