다른 블로그 포스팅을 보면서 공부한 것을 정리한 글입니다. Convex Hull Trick은 특정 형태의 점화식을 사용하는 다이나믹 프로그래밍을 빠르게 계산하기 위한 방법입니다. 점화식은 다음과 같습니다. $$D_i = \min_{j B_b$) $D_i$의 최솟값을 구하기 위해 그래프의 개형을 구해봅시다. $i$가 같을 때는 $A_i$도 같은 값이니 $x$축을 $A_i$로 하여, $y = B_j \times x + D_j$를 그리면 다음과 같습니다. $j$가 커질 수록 직선의 기울기 $B_j$는 감소합니다. $y$축과 만나는 점인 $(0, D_j ..