[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) 로 구할 수 있다.

 

 

 

 

	import sys
	import math
	#sys.stdin = open('input.txt')
	t = int(sys.stdin.readline())
	for _ in range(t):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	# i번째 페이지까지의 연속합
	cumsum = {-1:0}
	for i in range(len(arr)):
	cumsum[i] = cumsum[i-1] + arr[i]
	dp = [[0 for _ in range(len(arr))] for _ in range(len(arr))]
	# gap : 시작페이지 - 끝페이지 간 거리.
	for gap in range(1, len(arr)):
	# start : 페이지 시작지점
	for start in range(len(arr)):
	# end : 페이지 끝지점
	end = start + gap
	# 범위를 벗어난 경우
	if end == len(arr):
	break
	dp[start][end] = math.inf
	for i in range(start, end):
	dp[start][end] = min(
	dp[start][end],
	dp[start][i] + dp[i+1][end] + cumsum[end] - cumsum[start-1]
	)
	print(dp[0][-1])

view raw [백준] 파일 합치기.py hosted with ❤ by GitHub