https://www.acmicpc.net/problem/13466
13466번: Endless Turning
Last week your little sister celebrated her birthday, and she was very pleased with her birthday present: a brand new scooter! Since then several times a day she goes for a drive, without telling anyone. She will leave the house, and go right on the pa
www.acmicpc.net
시작점과 정수 N, R개의 직선이 주어진다. 시작점에서 직선을 따라 가다가 교차점을 만나면 오른쪽으로 돈다. N번 회전을 했을 때 어느 직선에 있는지 찾는 문제다.
N이 10^10이나 되기 때문에 단순한 시뮬레이션은 어려울 것처럼 보인다. 그런데 직선이 100개로 매우 적기 때문에 같은 교차점을 계속 순회할 것이라고 추측해 볼 수 있다.
잘 생각해 보면 교차점에서 무조건 오른쪽으로만 회전하므로 지나간 경로는 볼록다각형 형태로 나타날 것이다. 100개의 직선으로 만들 수 있는 꼭짓점이 가장 많은 볼록다각형 즉, 최대한 다양한 교차점을 지나는 경로는 100각형 형태다. 따라서 최대 100개의 교차점만 지나간다는 뜻이고, 시작점으로 돌아올 때까지만 시뮬레이션을 할 수 있다.
R이 작으므로 O(R^2)으로 각 직선끼리의 교점을 다 구한다. 각 직선마다 어느 지점에서 누구와 교차하는지 저장해 두고, 그 교점으로 정렬해두면 쉽게 구현할 수 있다.(vector<Cross> adj[]) lower_bound() 또는 upper_bound()를 잘 활용하면 어떤 직선에서 교점을 알 때, 그 교점에 바로 왼쪽이나 오른쪽으로 인접한 다른 교점을 O(log(R))에 찾을 수 있다.(Cross getNext(const Cross& me, int& dir)) 찾은 새로운 교점에 연결된 다른 직선에 대하여, 같은 방식으로 인접한 또다른 교차점을 찾아 나가면 된다. 시작한 직선으로 돌아올 때까지를 한 사이클이라고 하면, 사이클의 N % (사이클 길이) 번째 직선이 답이다.
모든 교점에 대하여 인접한 교점을 찾는데 총 O(R log(R))이지만 맨 처음에 모든 직선에 대한 교점을 만드는데 O(R^2)이므로, O(R^2)으로 해결할 수 있다.
코드
'알고리즘 > BOJ' 카테고리의 다른 글
| 2125번: 좀 (0) | 2021.04.23 |
|---|---|
| 15004번: Bearly Made It (4) | 2021.04.15 |