[BOJ 23889] 백준 23889번 - 돌 굴러가유

January 3, 2022

1. 문제

$23889$. 돌 굴러가유 (GBS Coding Contest 2021 Open E번)

백준 23889번 - 돌 굴러가유 (https://www.acmicpc.net/problem/23889)

문제의 예시를 통해 설명하고자 한다.

N=7, M=2, K=3 2 5 3 7 1 6 8 1 4 5

돌이 굴러가기 시작하는 마을의 위치에 벽을 설치해야 돌이 한 번도 굴러가지 못하게 막을 수 있어 가장 많은 모래성을 지킬 수 있다. 따라서 $1, 4, 5$ 중에 두 곳에 벽을 설치하면 된다.

이제 벽을 설치할 수 있는 곳을 기준으로 나누어서 모래성을 얼마나 막을 수 있는지 합을 구한다. 즉, 2 5 3 / 7 / 1 6 8 이렇게 나누어진다.

사실 벽은 세 위치 중 두 곳만 설치되므로 벽이 $1, 5$에 설치된다고 가정하였을 때, $1$에 벽을 설치하면 $2+5+3=10$만큼 막는 것이 아니라 $2+5+3+7=17$만큼 막을 수 있다.

그러나, $4$에 벽이 설치되지 않은 만큼 $4$의 돌이 손해를 주므로 $7$만큼 손해를 본다. 따라서 벽을 막지 않음으로써 돌이 굴러가서 입는 손해까지 포함해서 계산하게 되면, 돌이 굴러가기 시작하는 위치 이전까지의 합을 계산하는 것과 동일하게 된다.

오른쪽부터 구간별 누적합을 구하고, 최대 모래성을 지킬 수 있도록 누적합이 큰 순서대로 $M$개의 위치에 벽을 설치하면 된다. 사전순으로 가장 빠른 답을 출력해야 하므로, 정렬할 때 누적합이 같으면 index가 작은 순으로도 정렬하는 작업이 추가로 필요하다.