10800. 컬러볼

요새 글을 안 쓰는 이유는.. 쓸 게 없어서. 마이보카 2.0을 만들고 있는데 딱히 쓸 거리가 없다. 뭐 Compose 강의라도 해봐?

10800번: 컬러볼

---

어디서 많이 본 듯한 게임의 설명이 나온다. 요약하면

• 어떤 공은 자신과 색깔이 다르면서 자신보다 작은 공을 사로잡을 수 있다.
• 각 공이 잡아먹을 수 있는 모든 공의 크기의 합을 구하고 싶다.

특정한 공 $b$가 사로잡을 수 있는 모든 공의 크기의 합을 구해 보자.

1. $b$보다 작은 공을 구한다. 구한 공을 $smaller$라고 부르자.
2. $smaller$의 원소 중 $b$와 색깔이 같은 공을 모두 구한다. 구한 공을 $samecolor$라고 부르자.
3. $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$보다 작은 공의 크기의 합)을 빼면 정답을 구할 수 있다. 과정이 은근히 복잡하므로 정신 똑바로 차리고 구현해야 한다.

---

사실 풀이가 잘 생각나지 않아서 답을 보려고 했는데, 마지막으로 생각한 아이디어로 맞혀서 기분이 좋다. 

 

존 벤틀리는 자신의 저서 《생각하는 프로그래밍》에서 (대략) 이런 말을 했다.

...이 책을 읽고 단 한 명의 프로그래머라도 생각하는 즐거움을 깨우쳤으면 한다.

열심히 생각하자.