3221 개미의 이동

일자로 된 나무에 개미가 올려져있고, 위치와 이동방향이 주어진다. 이동하다가 나무 양 끝이나 다른 개미를 만나면 바로 방향을 바꿔 이동한다 할 때, T초 후 개미의 위치를 구하는 문제이다.

이 문제를 푸는 핵심은 바로 개미 이동의 성질이다. 예를들면 개미가 위치 P 에서 왼쪽으로 이동한다 할 때, 왼쪽 끝에 도달하는 시간은 P초일 것이다. 그리고 그것은 그 앞에 어떤 개미가 막고 있던지 마찬가지이다. 사실 현재 개미가 P초 만에 도달하는것은 아니고, 개미가 부딫힘으로 인해 다른 개미에게 자신의 방향을 넘겨주기 때문에, 다른 개미가 결국 P초에 왼쪽 끝으로 도달하게 된다.

따라서 개미를 한쪽 벽으로 보내고, T초를 길이로 나누게 되면 나눈값이 짝수일땐 개미는 제자리, 홀수일땐 반대편 벽에 있게 되고, T초를 길이로 나눈 나머지를 거기서 더해주면 T초후 개미의 위치를 구할 수 있다.

소스