백준 17078번 원 위의 개미

문제

택희는 원 하나를 갖고 있고, 그 원의 둘레를 일정한 속도로 기어다니는 개미 M마리를 키우고 있다. 각 개미들의 크기는 무시할 수 있을 정도로 매우 작다.

어느 날 택희는 원주를 N(≥M)등분하는 점을 찍고, 각 지점에 시계방향으로 1, 2, 3, …, N의 번호를 붙였다. 각 지점의 번호를 시계방향으로 읽으면 1, 2, 3, …, N이 되며, N번 지점 다음에는 1번 지점이 있게 될 것이다. 그 후, 모든 개미가 서로 다른 어떤 지점 위에 있도록 개미들을 놓았다. 개미들은 시계방향 또는 반시계방향의 초기 방향을 바라보고 있으며, 택희가 “시작”을 외치면 모든 개미들은 바라보고 있는 방향으로 이동하게 된다. 시작 시각은 0이며, 그 이후 정확히 1초마다 개미들은 다음 지점에 도착한다.

모든 개미는 동일한 속력으로 이동하다가, 서로를 마주칠 경우 그 즉시 방향을 바꾸어 돌아가게 된다. 개미들은 무한히 움직이며 택희가 찍은 N개의 점을 밟고 지나다니게 될 것이다.

택희는 개미들의 초기 위치와 방향에 따라, 같은 시간동안 상대적으로 조금 더 많이 밟히는 지점들이 있을 것이라 생각했다. 하지만 개미들은 멈추지 않기 때문에, 실제로 그런 지점이 있는지는 확인할 수가 없었다.

개미들은 시각 0에 자신이 서 있는 지점을 밟고 있으므로, 개미가 초기에 서 있는 모든 지점은 시각 0에 밟힌 횟수가 1이며, 아닌 모든 지점은 시각 0에 밟힌 횟수가 0이다. 또한, 개미 두 마리가 동시에 어떤 지점을 밟을 경우, 그 지점은 그 시각에 두 번 밟힌 것으로 센다.

택희는 자신이 세운 가설을 실험할 프로그램이 필요하다고 판단하였다. 정확히는, 어떤 지점 P가 X번 이상 밟히게 되는 최초의 시각이 여러 개 궁금해졌다. 택희를 위해, 이러한 질의를 빠르게 해결해 줄 프로그램을 작성해보도록 하자.

문제풀이

사용한 알고리즘 : 이분탐색

(0) 생각

 개미들이 부딪치면 완전 탄성충돌을 합니다.

 이것을 잘 생각해보면, 그냥 개미는 충돌이 없이 진행한다고 생각해도 됩니다.

 따라서 N초 후 ( 개미 한마리가 한바퀴 도는데 N초 걸림 ) 모든 지점은 M번 밟히게 됩니다.

(1) 코드 29~36

 위 생각에 따라, cnt = q*M + r 만큼 밟힌다고 생각합니다. ( 단 0 < r <= M )

 즉, 어떤 지점이든 q*M 번만큼 밟히는 건 q*N 시간 만큼이 필요합니다. 

 추가로 r 만큼 밟히는 시간만 구해주면 되는 것이죠.

 단, cnt가 M의 배수인 경우, r = M 으로 생각해 줄 것입니다.

 모든 지점이 N 시간 주기로 M번씩 밟히는 것은 맞습니다만, 각 지점마다 N주기 중 밟히는 시간이 다르기 때문입니다.

 예를 들어 N=4, M=2 이고, 1번 위치에 개미가 시계방향, 3번 위치에 개미가 반시계방향일 때 

 모든 위치는 4초마다 2번씩 밟히지만, 4초의 주기 속, 각 지역이 밟히는 시간은

지역	1	2	3	4
2번 밟히는 시간	2초	1초	2초	3초

 일 것입니다.

(2) 코드 38~71

 위에서 언급한 추가로 밟히는 r 번에 걸리는 시간을 계산합니다. ( 0 < r <= M )

 어떤 x 지역이 r만큼 밟히는 시간을 이분탐색으로 찾습니다.

 x에서 k만큼 떨어진 지역에 있는 개미가 x지역을 밟으려면 k 초의 시간이 걸릴 것입니다.

 최소 0, 최대 N-1 ( x에서 최대로 떨어진 지역과 x와의 거리는 N-1 입니다.) 으로 놓고,

 r번만큼 밟히려면 몇 초가 ( 얼마만큼의 거리가 ) 필요한지 계산합니다.