[python 파이썬] 백준 11066번 파일 합치기

DP 좋은 문제 추천

https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C

문제

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

풀이

정답 비율이 51.703 % ? 이건 사기다. 난 보자마자 불가능한 문제란 생각이 들었고 나중에 풀이를 봐도 이해가 가질 않았다. 연쇄행렬곱셈과 크누스 알고리즘 이라는 처음 들어보는 것들로 풀어야한다고 했다. 정말 정말 멘붕이었고 정답률도 높아서 더더 멘붕이었다.

무엇보다도 C++로 풀면 크누스 알고리즘으로 풀지 않고 연쇄행렬곱셈 풀이로 풀어도 시간 초과가 뜨지 않는다는데 python 은 시간 초과가 나와서 크누스 알고리즘으로 풀어야한다고 한다. 

나는 크누스 알고리즘까지는 아직 이해하지 못할거라고 판단하고 연쇄행렬 곱셈 방식으로 풀이를 봤고 여러번 다시 풀어봤다. 그랬더니 조금 이해가 가는 것 같다. 

다른 풀이들을 보니까 진짜 python 자료가 부족하단것도 알게 되었고 난 삼중for 문 도는것도 이해가 가지 않았는데 그 부분에 대한 설명은 전혀 없었다. 그래서 여기에 적어보려고 한다. 

먼저 코드

import sys
input = sys.stdin.readline
MAX = sys.maxsize

t = int(input())

def solve():
 n = int(input())
 file = list(map(int, input().split()))
 dp = [[0]*n for _ in range(n)]
 sum = [0]
 for f in file:
 sum.append(sum[-1]+f)

 for d in range(1,n):
 for i in range(n-d):
 j= d+i
 dp[i][j] = MAX
 for k in range(i,j):
 dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i])
 print(dp[0][n-1])



for i in range(t):
 solve()

일단 첫번째로 중요한것 : dp를 2차원 리스트로 만드는것이다. 시작점과 끝점을 정해준다고 생각하면 될듯.

두번째로 중요한것

C1=40 , C2=30, C3=30, C4=50일 때,

sum = [0, 40, 70, 100, 150]이 된다.

이것을 구해주는 이유는 dp 구할때 최소연쇄행렬곱셈 알고리즘을 응용하기 위함이다.

최소 연쇄 행렬 곱셈이라는 것은 여기 링크에서 짧게 다뤄놨으니 간단히 보고 오는것 추천 !

ex)

dp[0][1] + dp[2][3]

(c1+c2)          (c3+c4)

(40 + 30) + (30 + 50) = 70 + 80 이고 이 둘을 합치는 비용은 150이므로 70 + 80 + 150 최종 답은 300이 된다.

이 150을 구하기 위해 sum[4] - sum[0] 을 진행했고 이것은 sum[j+1] - sum[i] 

최종 점화식은 dp[i][j] = dp[i][k] + dp[k+1][j] + sum[j+1] - sum[i]

여기서!! 내가 이해 안간 부분은 왜 삼중for 문에 d 가 왜 나오고 i 는 왜 n-d 까지? j는 왜 또 더해 .... 이부분!

먼저 j = n 이 되어야한다. 왜냐하면 마지막 for 문에서 range(i,j) 이기 때문에 끝까지 돌리려면 j = n

다음으로 i 의 범위는 0 <= i < j 이므로 0 <= i < n 이 된다. 

i는 계속 변화해야하는데 j는 고정? 그렇기때문에 d 라는 변수를 새로 만들어준것이다. 

j = i + d 로서 변화하는 i에 맞춰서 d를 더해주면 j는 고정이 되기 때문에 

i = n - 1 ---> d = 1

i = n - 2 ---> d = 2

i = n - 3 ---> d = 3

.

.

.

i = 0      ---> d = n

그래서 저 코드를 돌리면 시간초과가 뜨고

pypy3 으로 돌려야한다. 

코드가 맞다면 pypy3 로 돌려도 상관없다고 한다.