[PS] 백준 3163번: 떨어지는 개미

|

문제

사실 이 문제는 이전에 한번 공부를 했던 문제였는데 4307번 개미 문제를 풀다가 아이디어가 생각이 안나서 다시 공부하게 되었다. 핵심 아이디어는 아래와 같다.

image1

개미 2마리가 좌표 $a$와 $b$ ($a\lt b$)에 위치한다고 하고 $x$를 그 중간좌표라고 하자.

  • $x$에서 충돌할 경우
    • ID가 +1인 개미는 $x-a$만큼 오른쪽으로 이동했다가 다시 왼쪽으로 $x$만큼 이동, $2x-a$만큼 이동한다.
    • ID가 -1인 개미는 $b-x$만큼 왼쪽으로 이동했다가 다시 오른쪽으로 $L-x$만큼 이동, $L+b-2x$만큼 이동하는데 $x-a=b-x$이기 때문에 $L-a$만큼 이동한다고 할 수 있다.
  • $x$에서 충돌하지 않는 경우
    • ID가 +1인 개미$L-a$만큼 이동한다.
    • ID가 -1인 개미$b=2x-a$만큼 이동한다.

따라서, 충돌할 때 방향을 바꾸지 않고 ID를 바꾼다고 생각할 수 있기 때문에 항상 왼쪽에서 떨어지는 개미의 수와 오른쪽에서 떨어지는 개미의 수가 같다는 것을 알 수 있다. 이 말은 개미가 떨어지는 시점은 충돌을 하든 안 하든 동일하다는 것이다.

문제는 두번째 아이디어였는데, 바로 개미의 ID 순서가 동일하다는 것이었다. 여기서 꽤 오랜시간을 썼는데 그 이유는 개미가 1초마다 움직인다고 생각해씩 때문이다 ㅠㅠ 문제에는 개미가 1초에 1mm만큼 움직있다고 했기 때문에 0.5초 동안 움직인 경우도 고려를 해야 하는데 이 부분을 빼먹었다.

그래서 자꾸만 왜 ID 순서가 동일하다는지 캐치할 수가 없었다.

image2

문제의 예시에서 +4와 -1의 좌표의 합이 짝수이기 때문에 충돌할 것이란 착각을 했는데 충돌의 개념은 좌표기준이 아니라 단순 방향기준이다!! 충돌하게 되면 방향이 바뀌기 때문에 ID 순서는 항상 동일한 값일 수밖에 없는 것이다. 위 그림에선 +5가 -1과 충돌하고 -5가 되며 -5는 +4와 충돌해서 -4가 된다. 또한 충돌한 -1이 +1로 되서 -3,-2와 충돌하면 -3과 -2는 +3과 +2가 된다. 따라서, 순서는 변하지 않는다.

따라서, 이 2가지 아이디어를 활용해서 아래와 같이 풀 수 있다.

  • 양수는 오른쪽 끝과의 거리, 음수는 왼쪽 끝과의 거리를 계산한다.
  • 거리기준으로 개미를 정렬한다.
  • 거리가 작은 것부터 보면서 양수면 오른쪽 끝의 개미가, 음수면 왼쪽 끝의 개미가 떨어진다.
    • 이 부분이 이해하기가 난해했는데 ID순서가 동일하다는 것을 이해하면 알 수 있다.
    • 음수 개미가 없으면 애초에 모두 양수니까 오른쪽 끝의 개미부터 떨어지는 것이 자명하다.
    • 양수 개미가 없으면 애초에 모두 음수니까 왼쪽 끝의 개미부터 떨어지는 것이 자명하다.
    • 서로 다른 개미가 하나라도 있을 경우, 충돌이 발생하므로 위 원리가 성립한다.

이 문제를 풀면서 배운점은 문제를 나만의 방식으로 해석해서는 안된다는 것이다. 처음에 좌표 기준으로 충돌의 정의를 했기 때문에 너무 많은 시간을 썼다. 이런 부분은 더욱 주의를 기울이도록 하자.