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