[Python] 백준 13975 파일 합치기 3

 

문제 분석

• 소설을 챕터마다 쓰는데 각 챕터는 다른 파일에 저장한다.
• 소설의 모든 챕터를 쓰고 나서 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다.
• 여러 챕터를 합치는 과정에서 두 개의 파일을 합쳐서 하나의 임시 파일을 만들고,
• 이 임시 파일이나 원래의 파일을 계속 두 개씩 합쳐서 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다.
• 두 개의 파일을 합칠 때 필요한 비용 = 두 파일 크기의 합
• 최종적인 한 개의 파일을 완성하는 데 필요한 비용의 총 합

 

정답 코드

실패

import sys, heapq
input = sys.stdin.readline

testcase = int(input())

for tc in range(testcase) :

    chap = int(input())
    cost = list(map(int, input().split()))
    heapq.heapify(cost)
    ans = 0

    while True :
        if len(cost) < 2 :
            print(heapq.heappop(cost) + ans)
            break

        c1 = heapq.heappop(cost)
        c2 = heapq.heappop(cost)
        ans = (c1+c2)
        heapq.heappush(cost, ans)

 

다른 정답 코드 1 : https://growth-coder.tistory.com/131

풀이

• dp + 삼중 반복문
• dp[x][y] : 인덱스 x파일부터 인덱스 y파일까지 하나의 파일로 합치는데 필요한 최소비용

1. x와 y가 동일한 경우

• 파일들의 크기를 다음과 같이 나열했다고 했을 때, 

4
40 30 30 50

• dp[0][0], dp[1][1] ... 과 같이 x와 y값이 동일하다면 하나의 파일을 의미하고 이미 하나의 파일이기 때문에 합칠 필요가 없다.
• 따라서 x와 y가 같은 위치의 값은 모두 0이다.

for i in range(n):
	dp[i][i] = 0 # 길이가 1인 것의 최소 비용

 

• 파일의 개수는 500개를 넘기지 않으므로, 파일들의 개수는 500을 넘기지 않는다.
• 파이썬에서 연산 횟수 1억번 = 1초라고 했을 때,  O(N^3)까지는 시간초과가 발생하지 않는다.

1초 = 약 1억 = 10^8

O(N^3)에서 가능한 N의 최대값을 추정하면 다음과 같다.
N^3 ≤ 10^8
N ≤ 10^(8/3)
N ≒464

따라서 N이 약 464 이하라면 1초 내에 실행이 가능하다.

 

• 현재까지는 길이가 1인 경우는 모두 구한 상황이다. (? : 뭔 길이가 1 ..?)
• 이제 길이가 2,3,... , n인 경우까지 모두 구해야 한다.
• 길이가 2인 경우를 보면, 두 개의 숫자가 합쳐지는 1가지 경우밖에 존재하지 않는다.
• 즉, dp[x][x+1]의 경우 둘을 더하면 된다.
• 길이가 3인 경우는 다음 2가지가 존재한다.

https://growth-coder.tistory.com/131

• 문제에서 주어진 길이는 15이고, 우리는 길이가 2, 3인 모든 범위에 대하여 최소 비용을 구해야 한다.
• 이제 길이가 15인 경우를 생각해보면서 공통적으로 적용할 알고리즘을 생각해야 한다.
• 길이를 증가시켜가면서 최소 비용을 구해왔기 때문에 길이가 10인 경우를 구할 때는 모든 범위에 대해서 길이가 1~14인 최소 비용을 알고 있다.
• dp[1][1] 값과 dp [2][15]의 합을 구하고, dp[1][2]값과 dp[3][15]의 합을 구하고 .. 이러한 과정을 반복해서 가장 작은 값을 구하면 된다.
• 그런데 dp[1][1] + dp[2][15]의 값은 한 페이지를 만들 때의 최솟값이 아닌 두 페이지를 만들 때의 최솟값이다.
• 그리고 두 페이지를 합칠 때의 비용은 1에서 15까지의 모든 비용의 합을 더한 값이다.
• 정확히는 dp[1][1] + dp[2][15] + sum(arr[1] ~ arr[15]) 와 같이 해당 범위의 모든 값을 더해주는 과정이 필요하다.

import sys
input = sys.stdin.readline

tc = int(input())

for _ in range(tc) :
    n = int(input())
    arr = list(map(int, input().split(())))

    subtotal = [0] * (n+1)
    subtotal[0] = 0

    for i in range(1, n+1) : # 누적합 구하기
        subtotal[i] = arr[i-1]
        subtotal[i] += subtotal[i-1]

    dp = [[1e9] * n for _ in range(n)]

    for i in range(n) :
        dp[i][i] = 0 # 길이가 1인 것의 최소 비용

    for i in range(2, n+1) : # 길이
        for j in range(n-i+1) : # 시작 인덱스
            for k in range(n-i+1) : # 하나하나씩
                dp[j][j+i-1] = min(dp[j][j+i-1], dp[j][k]+dp[k+1][j+i-1]+subtotal[j+i]-subtotal[j])
                
    print(dp[0][n-1])

 

다른 정답 코드 2 : https://velog.io/@seung_min/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-11066%EB%B2%88-%ED%8C%8C%EC%9D%BC-%ED%95%A9%EC%B9%98%EA%B8%B0

• dp 문제이다.
• 핵심은 dp[i][j]를 i번째 파일부터 j번째 파일을 합쳤을 때 최솟값이라고 두고 푸는 것이다.
• dp[1][2], dp[2][3], dp[3][4], ... dp[i][i+1]은 연속된 두 개의 파일을 합치는 것으로 파일 i와 i+1의 크기를 단순히 합친 것과 같다.
• dp[1][4]와 같은 경우 dp[1][1]+dp[2][4], dp[1][2]+dp[3][4], dp[1][3]+dp[4][4] 다음과 같은 경우의 수가 나온다.
• 즉, 위의 경우 중 최소값을 찾은 뒤 sum을 이용해 1번부터 4번 파일까지의 크기를 합하면 dp[1][4]값을 구할 수 있다.

import sys
input = sys.stdin.readline

def solve():
    K = int(input())
    arr = [0] + list(map(int, input().split()))

    # dp[i][j]는 i번째 파일부터 j번째 파일을 합치는 최소값
    dp = [[0]*(K+1) for _ in range(K+1)]

    # 먼저 dp[i][i+1]을 구한다. 즉, 두 파일이 연속으로 되어있을 때의 합을 구하는 경우만 dp에 저장한다.
    for i in range(1, K+1):
        for j in range(1, K+1):
            if j==i+1:
                dp[i][j] = arr[i] + arr[j]

    # dp의 맨 밑에서부터 위로 올라오면서 dp를 채워 나간다.
    # dp[1][4]는 dp[1][1]+dp[2][4], dp[1][2]+dp[3][4], dp[1][3]+dp[4][4]와 같은 경우의 수를 가진다.
    for i in range(K-1, 0, -1):
        for j in range(1, K+1):
            if dp[i][j] == 0 and j>i:
                dp[i][j] = min([dp[i][k]+dp[k+1][j] for k in range(i,j)]) + sum(arr[i:j+1])
    
    print(dp[1][K])

T = int(input())
for _ in range(T):
    solve()

 

다른 정답 코드 3

heapq

import sys
import heapq

def min_merge_cost(k, files):
    # 최소 힙에 파일 크기들 넣기
    heapq.heapify(files)

    total_cost = 0  # 총 비용 누적

    # 파일이 하나만 남을 때까지 반복
    while len(files) > 1:
        # 가장 작은 두 개의 파일을 선택
        first = heapq.heappop(files)
        second = heapq.heappop(files)

        # 두 파일을 합친 비용 계산
        merge_cost = first + second
        total_cost += merge_cost  # 비용 누적

        # 합친 파일을 다시 힙에 넣음
        heapq.heappush(files, merge_cost)

    return total_cost


# 입력 처리
def main():
    # 테스트 케이스 개수
    T = int(sys.stdin.readline().strip())

    results = []
    for _ in range(T):
        # 파일 개수 입력
        K = int(sys.stdin.readline().strip())

        # 파일 크기 리스트 입력
        files = list(map(int, sys.stdin.readline().strip().split()))

        # 최소 비용 계산
        results.append(str(min_merge_cost(K, files)))

    # 결과 출력
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    main()

 

 

2회차 - 25.03.27

import sys, heapq
input = sys.stdin.readline

tc = int(input())

for _ in range(tc) :
    n = int(input())
    chap = list(map(int, input().split()))

    heapq.heapify(chap)

    cost = 0

    while chap :
        if len(chap) > 1 :
            ch1 = heapq.heappop(chap)
            ch2 = heapq.heappop(chap)

            cost += (ch1 + ch2)
            heapq.heappush(chap, (ch1+ch2))

        else :
            # last = heapq.heappop(chap)
            # cost += last
            break

    print(cost)