[BOJ 8874] 웜뱃

https://www.acmicpc.net/problem/8874

IOI 2013 Day 1의 마지막 문제였다. 계절학교 첫 날에 문제를 보자마자 곧바로 스포당한 안타까운 문제이다.

일단은 보통의 세그먼트 트리 문제의 아이디어를 쓴다.

어떠한 자료구조라도 결합법칙을 만족하는 적절한 합치는 연산이 정의되어 있다면 세그먼트 트리에 넣을 수 있다.

라는 점이 강조되었다. 즉, 이 문제와 같이 1차원 범위(높이)의 데이터를 구하고, 각 데이터가 절반으로 나눈 데이터들을 적절히 합함으로써 얻어질 수 있다면, 세그먼트 트리를 통해서 얻을 수 있을까 하고 생각할 수 있게 된다. 사실 세그먼트 트리는 굉장히 멋진 자료구조인 것이, 노드의 구조와 합치는 연산만 제대로 생각하고 구현해서 넣어주면 트리님이 다 알아서 해준다! "세그먼트 트리는 분할 정복을 메모이제이션하는 것"이라는 조교님의 말이 기억에 남는다.

이 문제에서는 세그먼트 트리를 관리하는데, [s, e]를 관리하는 세그먼트 트리는 C*C의 행렬을 들고 다닌다. 행렬의 각 엔트리 (i, j)는 (s, i)에서 (e, j)로 가는 최단(웜뱃을 가장 적게 만나는) 경로를 담고 있다. 업데이트 시마다 값을 바꾸어주고 그 값을 관장하는 리프의 조상들만 업데이트해주는 형식으로 관리하면 될 것 같다. 하지만 이 문제는 평범한 문제등레서는 볼 수 있는 두 가지 난관에 봉착하게 된다.

1. 너비가 $C=200$이지만, 그래도 두 노드를 합치는 시간이 $C^3$ 이라는 너무한 시간이 든다:

이것을 분할 정복 최적화와 유사한 아이디어(나는 동일하다고 생각한다)를 써서 해결한다. (i, k)를 가는데 중간에 j를 들렀다면, k'<k에 대해 (i, k')를 갈때는 j'<=j인 j'를 들른다는 것이다. 이를 통해 |i-k|가 큰 것부터 iterating하면서 풀거나, (jstart, jend, kstart, kend)를 들고 다니는 재귀를 각 i에 대해서 돌리는 방법으로 $C^2$ 시간만에 노드를 합칠 수 있다.

2. 노드의 크기가 160kb나 되어서, 노드를 $2R = 10000$개나 들고 다니면 메모리가 넘는다..!:

메모리 가지고 장난치는 특이한 문제이다. 이 점 때문에 일정 수준 이상 작은 노드는 잘라내야 된다. 어차피 시간 제한은 20초로 넉넉한 편이다. 일종의 메모리와 속도의 트레이드오프? 이 부분 때문에 구현이 까다로워지는 면이 있기는 한데, 그것을 적절한 구현으로 메워주면 된다. 다음과 같이 해결한 사람들을 봤다.

a. (나의 경우) 원래의 세그먼트 트리와 똑같이 하되, 메모이제이션하는 인덱스를 제한시켜 그 이후의 인덱스는 모든 노드를 끝까지 들어가서 계산하도록 함:

 - 이렇게 하면 코드가 일관성 있게 짤 수 있어서 좋기는 한데, 더러워지는 것이 더 큼.

b. 범위의 크기가 작은 노드를 얻거나 업데이트할 때에는, 그냥 그 범위 안의 행렬들을 순차적으로 합쳐가면서 그 노드를 얻었음.

 - 이렇게 하면 두 가지 경우로 나누어지긴 하지만, 두 경우 모두 짧고 우아하게 짤 수 있음

c. 그냥, 버킷 방법을 씀.

 - 사실은 이 방법을 쓰는 사람이 최종 승자이다. 처음부터 메모리와 시간 모두 옳은 길로 와서, 위와 같은 이상한 짓을 안해도 된다!

구현이 중요한 문제였다. 풀이를 알고도 어떻게 구현해야 될 지 앉아서 생각을 꽤 해야 했다. 그래서 짜고도 디버깅을 한 시간 이상 했다..ㅠ