[백준] 11066번 : 파일 합치기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 여러 개의 파일을 하나의 파일로 합치는 과정에서 필요한 총 비용을 구하는 문제이다.

해당 문제의 핵심은 파일을 합치는데 필요한 최소 비용을 구하는 것이다.

문제의 첫 번째 예시를 살펴보면 각 파일의 크기가 40, 30, 30, 50 일 때, 파일을 하나로 합칠 수 있는 방법은 총 5가지이다.

5가지 방법 중 최소 비용인 300을 구하는 것이 문제의 핵심이 된다.

 

문제를 해결하기 위해서는 2개의 파일을 1개의 파일로 합치는 과정을 최종 1개의 파일이 될 때까지 반복해야 한다.

이를 다시 생각해 보면 최종 결과가 최적의 경우일 때, 이전의 2개의 파일을 1개의 파일로 합치는 2개의 파일 또한 최적의 경우이어야 한다.

결과가 최적의 경우일 때, 이전 결과도 최적의 경우이어야 한다는 점에서 다이나믹 프로그래밍 알고리즘을 떠올릴 수 있다.

다시 말하면, 만약 파일이 n개일 때 최종 2개의 파일을 1개의 파일로 합치기 전 각 2개의 파일이 최적의 경우이어야 한다.

 

다이나믹 프로그래밍 알고리즘을 활용해 문제를 해결하려면 각 경우별 최적의 결과를 저장할 2차원 배열(dp)을 생성해 주고 각 시작 파일부터 마지막 파일까지의 파일을 합칠 때 필요한 최소 비용을 지정된 위치에 저장한다.

dp[start][end]의 값은 start 번 파일부터 end 번 파일을 하나로 합칠 때 필요한 최소 비용을 의미한다.

dp[start][start]의 값은 파일이 합쳐지지 않으므로 0이 될 것이다.

dp[start][end]가 최종 결과를 의미할 때 각 이전의 2개의 파일은 중간 지점을 두어 start부터 중간 지점까지 최소 비용과 중간 지점 이후부터 마지막까지 최소 비용을 또 구해 최종 dp[start][end] 값을 구한다.

 

또한 두 파일을 합치는 비용 이외에 합쳐지는 각 파일의 비용도 고려해야 한다.

예를 들어 (A + B) + C의 방법을 파일을 합치는 것이 최적의 경우라고 할 때, A와 B를 합치고 합쳐진 AB와 C를 합쳐야 한다. 따라서 최종 비용은 (A + B) + (AB + C)가 된다.

이를 풀어서 나타내어 보면 AB 최소 비용 + (A + B + C)로 나타낼 수 있다.

여기서 A + B + C 같은 각 합쳐지는 파일의 합을 매번 구한다면 이 또한 많은 시간을 소요해야 할 것이다.

하여 1번 파일부터 각 파일까지의 누적합을 저장하는 배열을 만들어 활용해 준다.

start부터 end까지 각 파일의 비용을 더한 값은 누적합[end] - 누적합[start - 1]으로 쉽게 구할 수 있다.

 

합쳐지는 파일의 개수를 늘려가며 최종 1개의 파일이 될 때까지 파일을 최소 비용으로 합쳐준다.

count는 start와 end의 차이로 count가 1이면 파일 2개를 합치는 것을 의미하고, 2이면 파일 3개를 합치는 것을 의미한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 테스트 데이터의 개수를 입력받는다. T = int(sys.stdin.readline())
3. 테스트 데이터의 개수만큼 반복한다. for _ in range(T)
   1. 해당 테스트에서 합칠 파일을 개수를 입력받는다. K = int(sys.stdin.readline())
   2. 인덱스가 0부터 시작하므로 편의를 위해 0번 인덱스에 0을 넣고 이후 각 파일의 크기를 입력받아 하나의 리스트로 저장한다. File = [0] + list(map(int, sys.stdin.readline().split()))
   3. 누적합을 저장할 배열을 만들고 마찬가지로 0번 인덱스에 0을 넣기 위해 파일 개수보다 1개 더 큰 배열을 만들고 초기화한다. Sum = [0] * (K + 1)
   4. 1번부터 마지막 파일까지 가져오며 누적합 배열을 완성한다. for i in range(1, K + 1): Sum[i] = Sum[i - 1] + File[i]
   5. 각 파일을 합칠 때 최소 비용을 저장할 2차원 배열을 생성하고 초기화한다. 여기서도 마찬가지로 0번 인덱스를 사용하지 않으므로 크기를 1씩 늘려서 생성해 준다. dp = list([0] * (K + 1) for _ in range(K + 1))
   6. 시작 파일과 마지막 파일의 차이를 1부터 파일 개수 전까지 반복하며 파일의 개수를 점차 늘려 파일을 합쳐준다. for cnt in range(1, K)
      1. 합칠 파일의 시작 파일은 1번부터 파일 번호 차이에 따라 반복하며 for start in range(1, K - cnt + 1)
         1. 마지막 파일은 시작 파일에서 파일 번호 차이만큼 뒤에 있는 파일을 의미한다. end = start + cnt
         2. 각 경우별 최소 비용을 저장할 변수를 생성하고 최댓값을 저장해 준다. MIN = sys.maxsize
         3. 파일의 중간 위치를 시작 파일부터 마지막 파일 전까지로 변경하며 각 2개의 파일을 하나의 파일로 합칠 때 최소 비용을 구한다. for mid in range(start, end): MIN = min(MIN, dp[start][mid] + dp[mid + 1][end])
         4. 구한 최소 비용에 합쳐지는 파일의 각 크기를 더해 최종 시작 파일부터 마지막 파일까지의 최소 비용을 저장한다. dp[start][end] = MIN + Sum[end] - Sum[start - 1]
      2. 최종적으로 1번 파일부터 마지막 파일까지 합한 최소 비용을 출력한다. print(dp[1][K])

3. 소스코드

import sys

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

    File = [0] + list(map(int, sys.stdin.readline().split()))
    Sum = [0] * (K + 1)
    for i in range(1, K + 1):
        Sum[i] = Sum[i - 1] + File[i]

    dp = list([0] * (K + 1) for _ in range(K + 1))
    for cnt in range(1, K):
        for start in range(1, K - cnt + 1):
            end = start + cnt

            MIN = sys.maxsize
            for mid in range(start, end):
                MIN = min(MIN, dp[start][mid] + dp[mid + 1][end])

            dp[start][end] = MIN + Sum[end] - Sum[start - 1]
            
    print(dp[1][K])