[백준 11066번] 파일 합치기 (Python3)

import sys
input = sys.stdin.readline
INF = 10**9

T = int(input())
for test in range(T):
  N = int(input())
  data = [*map(int,input().split())]
  
  sumlist = [0]
  for i in range(N):
    sumlist.append((sumlist[-1]+data[i]))
  
  DP = [[INF]*N for i in range(N)]
  for i in range(N):
    DP[i][i] = 0
    
  for k in range(1,N):
    for i in range(N-k):
      for j in range(i,i+k):
        DP[i][i+k] = min(DP[i][i+k],DP[i][j]+DP[j+1][i+k]+sumlist[i+k+1]-sumlist[i])
  
  print(DP[0][N-1])

행렬 곱셈 순서 [백준 11049번] 행렬 곱셈 순서 (Python3) (tistory.com) 와 완전히 동일한 방법으로 풀 수 있다.

딱 하나 차이라면 누적합 리스트를 만들어서 데이터를 합칠 때 사용해주어야 한다는거 정도

 

그런데 이 문제를 시간복잡도 O(N^2)으로 풀 수 있는 방법이 있다고 한다. 제출한 코드 중에서 유독 시간이 적게 걸린 코드가 있어 체크했더니 크누스 최적화라는 기법을 이용하였다. 이에 대해서도 한번 알아봐야겠다.

 

 

오늘의 교훈) 크누스 최적화에 대해서 알아보자