Convex Hull trick 란 Convex Hull trick 란 Convex Hull(블록껍질) 알고리즘과는 다른 알고리즘이다. 최적의 값을 찾아가는 형태가 Convex Hull 을 닮아서 Convex Hull trick 라고 알려져 있는데~ Convex Hull Optimization 이라고도 한다. 이 알고리즘은 특정 점화식 꼴을 가지는 동적계획법에서 시간을 줄이는 방법이다. 일차 함수식이 위와 같이 여러개가 들어 오는 경우 각 x의 입장에서 최솟값을 찾는 알고리즘 동적알고리즘에서 다음과 같은 형태의 점화식 작성시 사용됨 dp[i] = min(dp[j] + a[i]b[j])( 0 13263번: 나무 자르기 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ....