링크

문제 요약

말뚝의 높이와 각 말뚝을 1칸 올리거나 내리는데 드는 비용이 입력으로 주어진다. 이때 말뚝을 적절히 조정하여 서로 같은 높이의 말뚝이 연속해서 K개 이상 나타나도록 만들 때 최소 비용을 구하여라.

관찰

K개 이상 나타나는 최소비용을 구하란 것은 K개의 연속하는 말뚝을 같은 높이로 만드는 최소비용을 만드는 것과 같음은 쉽게 알 수 있다. 1번부터 K번 말뚝까지를 같은 높이로 만드는데 드는 최소비용을 구하는 문제를 먼저 해결해보도록 하자. 만약 이 값을 구하는데 드는 시간이 충분히 작다면, 이 과정을 나머지 구간에 대하여도 시도해보면 문제가 풀릴 것이다.

$f_i(x)$ 를 $i$ 번째 말뚝을 높이 $x$로 만드는데 드는 비용이라고 하자. 해당 함수는 아래와 같이 표현된다.

\[f_i(x)= \begin{cases} -B_i(x-H_i) & (x\leq{H_i}) \\ A_i(x-H_i) & (x>H_i) \end{cases}\]

해당 함수의 그래프를 그려보면 V자 모양이 나오게 되고, 위와 같은 일차함수들을 이어서 만든 아래로 볼록인 함수는 그들을 더한 결과물도 일차함수로 이루어진 아래로 볼록인 함수이다. 그 이유는 아래 Lemma가 성립하므로 해당 증명 과정과 수학적 귀납법을 이용하여 증명할 수 있다. 당연히 역으로 위로 볼록한 경우를 더한 결과물들도 성립한다.

Lemma) 직선으로 이루어진 아래로 볼록인 두 함수를 더하면 그 결과물도 아래로 볼록이다.
Proof )
각 함수를 기울기가 변하는 시점단위로 구간을 쪼개어 각각의 기울기를 $a_1, a_2, \cdots{} , a_k$ 와 $b_1, b_2, \cdots{} , b_k$ 라고 하자.
각 함수는 아래로 볼록하므로 $a_1\leq{}a_2\leq{}\cdots{}\leq{}a_k$ 와 $b_1\leq{}b_2\leq{}\cdots{}\leq{}b_k$ 가 성립한다.
따라서 이를 더한 결과물인 $a_1+b_1\leq{}a_2+b_2\leq{}\cdots{}\leq{}a_k+b_k$ 가 성립한다.

또한 그 결과물은 기울기가 0인 구간이 존재하는 경우, 값이 극값을 가지게 됨이 자명하다. 즉, 해당 함수는 삼분 탐색에 적절한 형태를 가짐을 알 수 있다. 이제 함수 값을 빠르게 구하는 경우만 생각하면 문제가 풀릴 것이다.

풀이

함수 값은 어떻게 빠르게 구할 수 있을까? 그 방법은 간단하다. 실제로 어떤 높이 $X$ 에 말뚝을 맞춘다고 한다면, 말뚝을 높여야 하는 경우와 낮춰야 하는 경우의 수식을 전개해보면 답이 있다. 편의상 1번부터 $M$번까지의 말뚝을 높여야 한다고 가정하고 수식을 전개하면 아래와 같다.

\[A_1(X-H_1)+A_2(X-H_2)+\cdots{}+A_M(X-H_M) \\ =(A_1+A_2+\cdots{}+A_M)X-(A_1H_1+A_2H_2+\cdots{}+A_MH_M)\]

위의 식에서 변하는 값은 앞의 값만 변함을 알 수 있다. 따라서 높이 $X$ 이하의 $A_i$ 값들의 합과, $A_iH_i$ 값들의 합을 알고 있으면 위의 식은 상수시간에 계산이 가능하다. 문제의 조건을 보면 높이는 최대 10만이므로 업데이트를 지원하는 구간 합 자료구조를 이용하면 빠른 시간에 계산이 가능할 것이다. 즉, 자신의 높이를 업데이트할 인덱스로 보고 앞서 언급한 값들을 업데이트 하면 된다. 이는 펜윅 트리나 합 세그먼트 트리를 이용하면 해결됨이 알려져있다. 같은 방식으로 말뚝의 높이를 낮춰야 하는 경우에도 위와 유사하게 해결이 가능하다.

따라서 삼분 탐색을 하는 과정에서 함수값을 계산하는데 $O(\log{100000})$ 의 시간이 걸리므로, 구간 1개의 답을 얻는데 $O(\log^2{100000})$ 이 걸린다. 이 과정을 슬라이딩 윈도우를 하며 나머지 구간에 대하여도 값을 구하면 모든 구간에 대하여 최솟값을 얻을 수 있고, 그 값들중 최솟값이 정답이다. 슬라이딩 윈도우에 시간이 $O(N\log{100000})$ 이 걸리므로 전체 시간 복잡도는 $O(N\log^2{100000})$ 이 된다.