문제 링크
https://www.acmicpc.net/problem/11066
풀이
그냥 값이 작은 것 두 개씩 묶어서 붙이는 방법은 '연속된 파일끼리만 붙일 수 있다' 는 조건 때문에 불가능하다.
top-down 식으로 생각을 해 보자. 만약 10개짜리를 뭉친 덩어리가 있다 했을 때 이 덩어리는 어디서 왔을까?
(1) + (2345678910)(12) + (345678910)(123) + (45678910)
...(123456789) + (10)
이렇게 아홉 가지의 경우의 수 중, 가장 비용이 적게 합칠 수 있는 수일 것이다.
만약 저 중에서 (123) + (45678910) 의 경우가 가장 비용이 적다고 했을 때 다시 물어볼 수 있는 것.
그럼 (123) 이랑 (45678910)은 또 어디서 왔음?
3개짜리를 1, 2개에서 또는 2, 1개에서 합친 것 중 작은 것에서 왔을 것이고, 7개짜리 역시 마찬가지다.
뭔가 같은 점화식이 반복 될 것만 같다.
점화식 세우기
dp[i][j]를 정의하기를,
i부터 j까지의 파일을 합칠 때 드는 최소 비용
으로 정의하였다. 그럼 우리가 구하는 것은 dp[1][n]이다. (n=파일 개수)
i부터 j까지를 통합해야 하는데 이 사이 어딘가에 경계선이 있다. 그 경계선을 k라고 하자.
그럼 i ~ k, k+1 ~ j 해서 두 덩어리가 나올 것이고 이 때 k의 범위는 i 이상 j 미만이다.
즉 k를 i부터 j까지 움직여서 구한 dp들 중 최솟값이 dp[i][j]가 될 것이다.
dp[i][j] = min(dp[i][k] + dp[k+1][j] for k in range(i, j))
여기에다가 i부터 j까지의 합을 더하면 될 것 같다.
그렇게 하여 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def f(a, b, s, dp) :
if a == b :
return 0
if b - a == 1 :
return s[b] - s[a-1]
if dp[a][b] != 0 :
return dp[a][b]
z = min(f(a, k, s, dp) + f(k+1, b, s, dp) for k in range(a, b)) + (s[b] - s[a-1])
dp[a][b] = z
return z
def solve() :
k = int(input())
arr = [0] + list(map(int, input().split())) # 각 파일의 비용을 담고 있는 리스트
s = [0] * (k+1) # 각 비용을 이용한 부분합을 담고 있는 리스트
s[1] = arr[1]
for i in range(2, k+1) :
s[i] = s[i-1] + arr[i]
dp = [[0] * (k+1) for _ in range(k+1)]
print(f(1, k, s, dp))
for _ in range(int(input())) :
solve()예제는 잘 통과한다. 그런데 제출하면 RecursionError가 뜬다. 저 뒤로 setrecursionlimit까지 해줬는데 시간 초과가 뜬다.
bottom-up 방식으로 구현하기
10개를 쪼갤 때 (1, 9), (2, 8) ... 을 호출하고, 저기서 (1, 9)에서 또 (1, 8), (2, 7) ... 을 호출하니까 당연히 시간 초과가 뜨지...
이 이후 멋진 풀이가 생각나지 않아서 구글링했다.
결론부터 말하자면 키포인트는 파일의 길이 였다. 2개짜리부터 시작해서 결국 n개를 모두 합치는 방법, 즉 bottom up 방식으로 풀어야 하는 것이었다.
-
파일의 길이에 따라 구간 길이를 먼저 정의한다. 총 구하고 싶은 파일의 개수를 k라 하면 길이는 2부터 k까지이다.
-
구간 길이에 맞게 구간을 나눈다. 구간 길이가 n이라면 1, 2, ... n부터 시작하여 k-(n-1), ... k-1, k까지 나온다.
-
구간 안에서 경계선을 잡아주고 최솟값을 구한다. (하위 길이를 먼저 채우면서 올라왔으므로 최솟값을 구하는 시간은 선형 시간만에 가능하다)
-
구한 최솟값에 구간의 누적합을 더해주고, dp 리스트에 기록한다.
-
최종적으로 구하는
dp[1][k]를 구한다.
최종 코드
import sys
input = sys.stdin.readline
def solve() :
k = int(input())
arr = [0] + list(map(int, input().split())) # 각 파일의 비용을 담고 있는 리스트
s = [0] * (k+1) # 각 비용을 이용한 부분합을 담고 있는 리스트
s[1] = arr[1]
for i in range(2, k+1) :
s[i] = s[i-1] + arr[i]
# 이렇게 넣어놓으면 i부터 j까지의 합을 s[j] - s[i-1]로 구할 수 있다.
dp = [[0] * (k+1) for _ in range(k+1)]
# dp[i][j]는 i번째 파일부터 j번째 파일까지를 합치는 데 필요한 최소 비용을 담고 있다
# 즉 우리가 구해야 하는 것은 dp[1][n]
for n in range(2, k+1) : # 길이. 최대 k까지 돌아야 하므로 range는 2, k+1
for i in range(1, k-n+2) : # 시작 위치. 길이가 n일때 1,2,...n 부터 시작해서 k-(n-1),...k-1,k까지 돈다.
#예를 들어 길이가 2면 k-1까지 돌아야한다.
dp[i][i+n-1] = min(dp[i][j] + dp[j+1][i+n-1] for j in range(i, i+n-1)) + (s[i+n-1] - s[i-1])
# j는 중간에 잘리는 위치. (i, i+n-1) 에서 j가 될 수 있는 것은 i부터 i+n-2까지.
# 그리고 뒤에 i부터 i+n-1까지의 부분합을 더해준다. (s 리스트 이용)
print(dp[1][k])
for _ in range(int(input())) :
solve()
길이를 먼저 구해야 하는 동적 계획법 문제에서 왕왕 나오는데 항상 생각하기가 어렵다.
이런 문제들을 최적 이진 검색 트리(Optimal Binary Search Tree) 라고 한다.
