나무 자르기

문제

높이가 a1, a2, ..., an인 나무 n개를 전기톱을 이용해서 자르려고 한다.

i번 나무에 전기톱을 사용할 때 마다 그 나무의 높이는 1만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다. 전기톱을 충전하는 비용은 완전히 자른 나무의 번호에 영향을 받는다. 즉, 높이가 0이 되어버린 나무의 번호에 영향을 받는다. 완전히 잘려진 나무의 번호 중 최댓값이 i이면, 전기톱을 충전하는 비용은 bi이다. 완전히 잘려진 나무가 없다면 전기톱은 충전할 수가 없다. 가장 처음에 전기톱은 충전되어져 있다.

나무의 높이 ai와 각각의 나무에 대한 충전 비용 bi가 주어졌을 때, 모든 나무를 완전히 자르는데 (높이를 0으로 만드는데) 필요한 충전 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109)

a1 = 1이고, bn = 0이며, a1 < a2 < ... < an, b1 > b2 > ... > bn을 만족한다.

출력

나무를 완전히 자르는 충전 비용의 최솟값을 출력한다.

 

예제 입력
5

1 2 3 4 5

5 4 3 2 0

 

예제 출력

25

 

문제 풀이 

이 문제를 잘 보면 마지막 bn은 항상 0이라는 것이다. 즉 bn까지 가기 직전의 최소 dp만 구해서 풀 면 되는 문제인 것이다. 

문제의 점화식은 dp[i] = bj * ai + dp[j] 라는 식이 나오게 된다. n의 제한은 10^9 임으로 n^2으로 시간복잡도를 구하게 되면 정말 풀기 힘든 문제가 된다.  이 문제를 풀기 위해서는 CHT라는 기법을 사용하면 된다. 

 

Convex Hull Trick(CHT) 

나무자르기 문제를 해결 하기 위해서는

Convex Hull Trick의 약자로 말 그대로 볼록껍질을 이용한 트릭이다. 

기울기가 주어진 직선들을 하나하나 구해 나가면서 새로 구해진 기울기가 직전 기울기 보다 크다면 이전 직선은 제거해 나가면서 최솟값을 찾게 해주는 하나의 볼록한 직선들의 집합을 구해내는 기법이라고 보면 된다. 

 

아래는 문제의 풀이 코딩이다. 

 

from sys import stdin

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

dp = [0] * N  # dp[i] = B[j]A[i] + dp[j]
linear_funcs = [] # 일차 함수의 모음집이다 위에서 언급한 CHT 즉 최솟값만을 포함하게 만드는 열쇠이다. 
fpos = 0

for i in range(1, N):
    #
    b0, dp0, x0 = B[i - 1], dp[i - 1], 0
    while linear_funcs:
        # linear_funcs에 저장될 일차 함수들은 특정 영역에서 다른 함수보다 최솟값을 가지도록 구성된다.
        # 반대로 말하면 x의 범위에서 다른 함수와 비교해 최솟값을 가지지 못하면 퇴출당한다. 여기서는 g값이 decreasing 하기 때문에, 퇴출 당할 일은 없다.
        b1, dp1, x1 = linear_funcs[-1]
        
        # 
        x0 = (dp1 - dp0) / (b0 - b1)  
        print( 'linear_funcs[-1]',  linear_funcs[-1], x0 )
        # x1은 현재 linear_funcs의 끝의 일차함수로 이전 일차함수와의 교점인 x1을 가지고 있다.
        # 만약 x0가 x1보다 크다면 b1의 기울기를 가진 함수는 b0의 기울기를 가진 함수에 가려지지 않는다. (= b1의 기울기를 가진 함수는 특정 구간에서 최솟값을 가진다)
        if x1 < x0:
            break
        # x1보다 작거나 같아 버리면, b1의 기울기를 가진 함수는 b0에 완전히 가려지기 때문에 퇴출당해야만한다.
        
        linear_funcs.pop()
    # b0함수는 무조건 기울기가 현재 linear_func의 일차함수들보다는 작기 때문에 현재로썬 최솟값을 가지는 구간이 있음을 확신할 수 있다.
    linear_funcs.append((b0, dp0, x0))

    x = A[i]
    # linear_funcs[i][2]은 i번째 일차함수가 i-1번째 일차함수과 교차한 지점으로, 해당 지점이 x보다 작은 교차점 중에서 가장 큰 교차점이 될 수 있도록 fpos를 1 더해준다.
    # 즉 새롭게 들어갈 dp[i] = a*x + b에 들아갈 새로운 x를 정리하기 위해 a,b값을 호출 하기 위해서 이다. 
    while fpos + 1 < len(linear_funcs) and linear_funcs[fpos + 1][2] < x:
        fpos += 1

    a, b, _ = linear_funcs[fpos]
    print( '점화식 기준, a, dp',fpos, a , b )
    dp[i] = a * x + b

print(dp[-1])

'''
점화식 기준, a, dp 0 5 0
linear_funcs[-1] (5, 0, 0) 10.0
점화식 기준, a, dp 0 5 0
linear_funcs[-1] (4, 10, 10.0) 5.0
linear_funcs[-1] (5, 0, 0) 7.5
점화식 기준, a, dp 0 5 0
linear_funcs[-1] (3, 15, 7.5) 5.0
linear_funcs[-1] (5, 0, 0) 6.666666666666667
점화식 기준, a, dp 0 5 0
25
'''