특정 DP 문제에서 다음과 같은 꼴의 식을 접할 수 있다. 보통의 경우, 각 (i, j)에 대해 모두 계산해 최솟값을 찾아줘야하므로 시간복잡도는 O(n^2)이다. 하지만 모든 j에 대해 B[j]>B[j-1]인 경우에는 시간복잡도를 O(nlogn)까지 줄일 수 있고 만약 모든 i에 대해 A[i]j이상인 모든 n에 대해서 A[i]B[j]+C[j]를 계산하는 과정은 f(x)=B[j]x+C[j]라는 고정된 일차함수의 A[i]에 대한 함숫값을 계산하는 과정과 같다는 것이다. j번째 직선을 나타내는 함수를 f_j(x)라고 하자. f_j(x) 들의 기울기인 B[j]가 점점 감소하므로 직선들은 아래와 같이 그려진다. 우리는 각각의 x에 대해 최솟값을 구해주고 싶으므로, 위 그래프에서 빨간 부분만 고려하면 된다. 빨간 ..
