Red Cut

절단 과정은 잎의 순서가 고정된 완전 이진 트리와 대응한다. 내부 정점이 담당하는 구간의 길이가 홀수일 때 그 정점의 경계가 붉다.

현재 존재하는 홀수 길이 조각의 수를 추적하면 가능한 붉은 절단 수를 얻는다.

• $N=2m$이면 $0\leq K\leq m-1$이다.
• $N=2m+1$이면 $1\leq K\leq m$이다.

홀수 길이 $2m+1$의 내부 경계에 대해 다음 집합을 증명 블록이라 하자.

$$\{1\},\{2,3\},\{4,5\},\cdots,\{2m-2,2m-1\},\{2m\}.$$

귀납적으로 모든 실현 가능한 붉은 경계 집합은 증명 블록 하나를 완전히 포함한다. 반대로 다음 조건은 모두 충분하다.

• 길이 $2m$에서는 크기가 $m-1$ 이하인 모든 경계 집합이 실현 가능하다.
• 길이 $2m+1$에서는 크기가 $1$ 이상 $m$ 이하이고 증명 블록 하나를 포함하는 모든 집합이 실현 가능하다.

충분성은 첫 절단으로 문제를 더 작은 짝수와 홀수 구간으로 나누는 강한 귀납법으로 보일 수 있다.

$N$이 짝수이면 가장 싼 $K$개 경계를 고르면 된다. $N$이 홀수이면 각 증명 블록 $B$를 강제로 포함하고, $B$ 밖에서 가장 싼 $K-|B|$개를 더한 값을 비교한다. 비용을 정렬하고 누적합과 각 경계의 정렬 순위를 저장하면 크기가 최대 $2$인 블록 하나를 $O(1)$에 평가할 수 있다.

전체 시간 복잡도는 $O(N\log N)$, 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5