BOJ 9244 - 핀볼 (및 Class 9 취득)

오래 눈여겨둔 문제이자 Class 9를 취득하기 위한 마지막 문제였다.

 

문제 요약

 

선분 \(N\)개가 주어진다. 이 선분들은 서로 교차하거나 만나지 않는다. 공은 \((x_0, \infty) \)에서 떨어지며, 선분을 만나면 선분을 따라 이동한다. 공의 최종 \(x\)좌표를 구하여라.

 

풀이

우선, 자명하게 각 선분의 다음 선분, 즉 어떤 선분에 떨어졌을 때 다음으로 도착하게 되는 선분은 정해져 있으며, 사이클을 이루지 않는다. 만약 각 선분의 다음 선분을 구한다면 간단한 시뮬레이션으로 문제를 해결할 수 있다.

따라서 문제의 핵심은 다음 선분을 구하는 것이다. 이를 위해서는 어떤 기준을 세워서 선분을 탐색하고 싶지만, 쉽지 않다. 두 선분의 우열을 두 선분만으로 구분할 수 없는 경우가 있기 때문이다.

구분할 수 있는 경우는 겹치는 \(x\)좌표가 존재할 때이고, 그렇지 않다면 두 선분의 우열은 두 선분만으로 알 수 없다.

 

그렇다면, 어떤 \(x\)좌표를 지나는 선분들만 모아놓은 상태에서는 우열을 구분할 수 있다는 뜻이 된다. 해당 \(x\)좌표에서의 \(y\)값을 비교해주면 된다.

이 상태를 유지하려면 어떻게 해야 할까? 그냥 \(x\)좌표 기준으로 스위핑을 해 주면 된다. 스위핑 과정에서 set에 들어 있는 선분들은 항상 특정 \(x\)좌표를 공유하며, 따라서 정렬 상태를 유지할 수 있다.

각 선분의 다음 선분을 찾는 것은 set에서 이분 탐색을 통해 구해주면 된다. 구현할 때 주의할 점이 몇 개 있지만, 생략하도록 하겠다.

 

이 문제를 통해 Class 9 취득에 성공했다. Class 9도 상당히 버거웠기에 10은 최소 \(N\)년 이후에 보지 않을까 싶다. 당분간은 얼마 남지 않은 D1을 목표로 그냥 공부하고 싶었던 주제들을 좀 살펴볼 예정이다. ICPC 대비한다고 나름 열심히 풀었는데 성과가 나오면 좋겠다.