[다이나믹 프로그래밍] ★★ 11066번 - 파일 합치기

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

(한줄평) 풀릴듯 하면서 풀리지 않아서 풀이를 보니 생각보다 더 복잡한 문제였다. 풀이를 봐도 쉽게 이해가 가지 않았기때문에 꼭 복습이 필요하다!

풀이 시간: 3시간 이내

 

1) 문제 해결 아이디어

소설을 구성하는 장의 수(k)와 k개의 파일의 크기(f)가 주어졌을 때 모든 장을 합치는데 필요한 최소 비용을 구하는 문제다. 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산해야한다.

 

<동작과정>

동작 과정은 크게 2가지 정도로 구분할 수 있다.

1. i ~ j까지 누적합 계산

 

2. (k-2)개의 대각선방향으로 각 칸의 i ~ j까지 최소 비용 구하기(각 케이스들 중 최소값을 구해 더함)

파란색 부분을 구하는 방법 자세하게 설명하자면 아래와 같다.

 

<점화식>

첫번째 오류. 시간초과

pypy3로 돌리니 통과했다.

 

[참고] https://data-make.tistory.com/402

[BOJ] 11066. 파일합치기(DP).py,.cpp

 

2) 소스코드

import sys
input = sys.stdin.readline

t = int(input())  # 테스트 케이스 수
for _ in range(t):
  k = int(input())  # 소설의 장 수(3이상 500이하)
  f = list(map(int, input().split()))  # k개의 파일 크기
  
  # i에서 j까지 합하는데 필요한 최소 비용
  d = [[0] * k for _ in range(k)]
  # 1. i에서 j까지 누적합 구하기(대각선으로 진행)
  for i in range(k - 1):
    # 각 행의 첫번째 값은 i ~ (i+1)의 합으로 초기화
    d[i][i + 1] = f[i] + f[i + 1]
    # i ~ j의 누적합
    for j in range(i + 2, k):
      d[i][j] = d[i][j - 1] + f[j]

  # (k-2)번 대각선으로 최솟값 구하기
  for n in range(2, k):
    for i in range(k - n):
      j = i + n
      # (i ~ x)의 최소 비용 + (i+1 ~ j)의 최소 비용 들 중에 최솟값
      costs = [d[i][x] + d[x + 1][j] for x in range(i, j)]
      d[i][j] += min(costs)

  print(d[0][k - 1])  # 모든 장을 합치는데 필요한 최소 비용

[참고] https://suri78.tistory.com/15

[백준알고리즘] 11066번: 파일 합치기 -Python