[BOJ] 3163번: 떨어지는 개미

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

만약 매 시간마다 개미 N개를 1씩 움직여서 시뮬레이팅하려고 하면 시간 내에 풀 수가 없습니다.

이 문제의 핵심은

1. 시간과 상관없이 개미가 막대 위에 놓여있는 순서는 변하지 않는다.(즉 개미 3, 개미 2, 개미 1 순서로 막대에 놓여있으면 서로간의 거리는 달라지더라도 놓여있는 순서는 유지된다.)

2. 두 개미가 부딪칠 때 경로를 반대로 가는 대신, 가던 길을 그대로 가되 ID만 서로 바꿔서 진행한다고 생각을 해도 상황은 똑같다. 즉 떨어지는 개미의 ID는 모르더라도 각 개미가 왼쪽, 오른쪽으로 언제 떨어지는지는 초기 상태부터 정해져있다.

이 두 가지를 염두해둔다면, k번째 떨어지는 개미가 왼쪽에서 떨어지는지 오른쪽에서 떨어지는지 알 수 있고 이를 알고나면 1번 성질에 의해 개미의 ID를 알 수 있습니다. 

https://github.com/encrypted-def/BOJ/blob/master/3163.cpp