Merge Alarm

길이가 $L$인 묶음의 표시값은 합치는 순서와 무관하게 항상 $L\bmod M$이다.

현재 존재하는 모든 묶음의 표시값 합을 $P$라고 하자. 경보가 없으면 $P$는 변하지 않고, 경보가 발생하면 정확히 $M$ 감소한다. 처음에는 $P=N$이고 마지막에는 $P=N\bmod M$이므로, 모든 합치기 순서에서 경보는 정확히

$$q=\left\lfloor\frac{N}{M}\right\rfloor$$

번 발생한다.

남은 핵심은 임의의 $q$개 경계를 경보 위치로 만들 수 있다는 사실이다. 길이 $L=qM+r$인 구간을 마지막으로 지역 경계 $k$에서 합치면 경보가 발생할 필요충분조건은 $k\bmod M>r$이다. 크기가 $\lfloor L/M\rfloor$인 목표 경보 집합 $S$에 대해, 왼쪽에 정확히 $\lfloor k/M\rfloor$개의 선택된 경계가 있고 $k$의 선택 여부가 위 조건과 일치하는 분할 경계 $k$가 항상 존재한다. 이 경계로 나누고 두 자식 구간에 귀납법을 적용하면 $S$ 전체를 실현할 수 있다.

따라서 가능한 경보 집합은 크기가 $q$인 모든 경계 부분집합이다. 비용이 가장 작은 $q$개 경계를 선택하면 최적이다. 비용을 정렬한 뒤 앞의 $q$개를 더한다. 시간 복잡도는 $O(N\log N)$이다.

Solution written by GPT5