[Python] 백준 11066. 파일 합치기

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

11066번: 파일 합치기

문제 자체도 난해한데, Python3의 느린 연산속도 때문에 시간초과까지 겹쳐서 푸는 데 정말 오래 걸렸다.

이 풀이는 PyPy3으로만 통과하며, Python3으로는 시간초과가 난다. C++이나 Java의 로직으로는 통과하지만...

 

전제: '인접한 페이지'끼리만 합칠 수 있다.

문제의 예시라면, C2와 C4를 바로 합치는 건 불가능하고,

C2 + (C3 + C4) 또는 (C2 + C3) + C4 형태로만 합칠 수 있다는 뜻.

 

DP로 풀 수 있는 문제유형.

예컨대 2페이지 ~ 4페이지까지를 합치는 최소비용은

min(C2 + (C3 + C4), (C2 + C3) + C4) 라고 볼 수 있다.

일반화하면 

 

i번째 파일부터 j번째 파일까지 합치는 최소비용을 table[i][j]로 정의하면

중간 어느 지점인 k에서 반으로 나눈 지점의 합이다.

table[i][j] = min(table[i][j], table[i][k] + table[k+1][j]) 가 된다.

 

여기에 '추가비용'을 생각해야 하는데, 

C2 ~ C4를 합치는 총 비용은

min((C2 + C3) 비용, (C3+ C4) 비용) + C2 + C3 + C4

형태이기 때문이다.

 

즉 table[C2][C4] = min(table[C2][C3]+C4, table[C3][C4]+C2) 인데,

다시 생각하면 min(table[C2][C3], table[C3][C4]) + sum(C2~C4)로도 생각할 수 있다는 점이다.

시작점에서 끝점까지의 연속합을 구해야 한다. 이 값은 sum(C2~C4) - sum(C2) 로 구할 수 있다.