백준 11066번 파일 합치기

백준 11066번 파일 합치기

문제 바로가기

코드

import sys

def dynamic(start, end):
  if dp[start][end] != 0:
    return dp[start][end]
  
  if start == end:
    cost = files[start]
    dp[start][end] = cost
    return cost

  prev_sum = 0
  cost = float('inf')
  for i in range(start, end+1):
    prev_sum += files[i]

  for v in range(start, end):
    cost = min(cost, prev_sum + dynamic(start, v) + dynamic(v+1, end))

  dp[start][end] = cost
  return cost

T = int(sys.stdin.readline())
result = []
dp = [[0 for _ in range(T)] for _ in range(T)]

for i in range(T):
  K = int(sys.stdin.readline())
  files = list(map(int,sys.stdin.readline().split()))
  dp = [[0 for _ in range(K)] for _ in range(K+1)]
  cost = float('inf')

  for v in range(K):
    cost = min(cost, dynamic(0, v) + dynamic(v+1, K-1)) 
  result.append(cost)
  
for r in result:
  print(r)

문제 해결

탐색

파일 합치는 문제는 각각 주어진 데이터를 '어떠한 형태로 쪼개는가'가 중요한 문제이다.

각각의 데이터를 받았을 때 재귀함수를 통해서 각각의 쪼개는 방식에 따라서 전부 구해보고 그중에서 최솟값을 선택하도록 알고리즘을 구성했다.

하지만 바로.. 시간초과

사실 쪼개는 방식에 따라서 계산값이 계속 달라지므로 무수한 형태가 나올 것이고 이를 전부다 계산하려면 시간이 오래걸리는게 당연하다.

따라서 일반적인 탐색 방법으로 풀게 된다면 의미없는 반복계산이 많아져서 문제를 풀 수 없겠구나..

DP

같은 방식으로 데이터를 탐색하여 최솟값을 구하는 과정은 똑같다. 하지만 의미 없는 반복계산을 줄이기 위해서 dp 배열을 만들고 (시작지점, 끝나는 지점)을 이용해서 계산을 할때마다 배열에 저장하는 방식을 선택했다.

만약 재귀함수를 도는 도중에 이미 dp 배열에 저장했던 계산이 나온다면 더이상의 계산을 하지 않고 dp 배열 값을 return 하도록 했다.

의미없이 반복되는 계산을 줄이자!