10800. 컬러볼
요새 글을 안 쓰는 이유는.. 쓸 게 없어서. 마이보카 2.0을 만들고 있는데 딱히 쓸 거리가 없다. 뭐 Compose 강의라도 해봐?
10800번: 컬러볼
첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N
www.acmicpc.net
어디서 많이 본 듯한 게임의 설명이 나온다. 요약하면
- 어떤 공은 자신과 색깔이 다르면서 자신보다 작은 공을 사로잡을 수 있다.
- 각 공이 잡아먹을 수 있는 모든 공의 크기의 합을 구하고 싶다.
특정한 공 $b$가 사로잡을 수 있는 모든 공의 크기의 합을 구해 보자.
- $b$보다 작은 공을 구한다. 구한 공을 $smaller$라고 부르자.
- $smaller$의 원소 중 $b$와 색깔이 같은 공을 모두 구한다. 구한 공을 $samecolor$라고 부르자.
- $smaller$의 크기의 합에서 $samecolor$의 크기의 합을 빼면 된다.
1번 과정
1번 과정에서 특정한 공 $b$보다 작은 공을 모두 구해야 한다. 그런데 매번 $O(N)$으로 구하면 시간 초과이므로 미리 다음의 값을 계산해 놓자.
$smaller[i]$: 크기가 $i$보다 작은 모든 공의 크기의 합
메모이제이션을 활용하여 다음과 같이 $smaller$를 계산할 수 있다.
$smaller[i] = smaller[i-1] + sizesum(i-1)$
이때 $sizesum(i-1)$은 크기가 $i-1$인 모든 공의 크기의 합이다.
2번 과정
$b$보다 작은 공을 모두 구하고, 구한 공에서 $b$와 색깔이 같은 공들을 찾아내려면 $O(|smaller|)$ 시간이 필요하다. 조금 더 빠르게 구할 수 없을까?
$b$와 색깔이 같은 공 중 $b$보다 작은 공을 구하는 게 훨씬 쉽다. 색깔이 같은 공끼리 크기의 오름차순으로 모아 놓고(``std::vector``의 배열이 적합하다), 이분 탐색을 통해 $b$보다 작은 공을 구하면 된다. 나는 ``std::lower_bound()``를 이용했다.
3번 과정
1번 과정에서 구한 값($b$보다 작은 공의 크기의 합)에서 2번 과정에서 구한 값($b$와 색깔이 같은 공 중 $b$보다 작은 공의 크기의 합)을 빼면 정답을 구할 수 있다. 과정이 은근히 복잡하므로 정신 똑바로 차리고 구현해야 한다.

사실 풀이가 잘 생각나지 않아서 답을 보려고 했는데, 마지막으로 생각한 아이디어로 맞혀서 기분이 좋다.
존 벤틀리는 자신의 저서 《생각하는 프로그래밍》에서 (대략) 이런 말을 했다.
...이 책을 읽고 단 한 명의 프로그래머라도 생각하는 즐거움을 깨우쳤으면 한다.
열심히 생각하자.