1) O(t) 방법 (40점)
개미의 좌표 (x,y)를 1시간 지날 때 마다 변화시키는 시뮬레이션을 돌려본다.문제에 주어진 입출력 예제 1에서 예를 들어보면 다음과 같다.
(4,1)→ (5,2) →(6,3)→(5,4) →(4,3)→(3,2)→ (2,1) → (1,0) → (0,1) 0시간 1시간 2시간 3시간 4시간 5시간 6시간 7시간 8시간2) 70점 방법
개미의 좌표 (x,y)를 격자 공간의 모서리, 꼭짓점에 닿을 상황으로만 변화시키는 시뮬레이션을 돌린다.문제에 주어진 입출력 예제 1에서 예를 들어보면 다음과 같다.
(4,1) → (6,3) → (5,4) → (1,0) → (0,1) 0시간 2시간 3시간 7시간 8시간3)O(1) 해법 (100점)
x좌표와 y좌표는 서로 독립적이므로, 서로에게 영향이 없고 따로 계산할 수 있다. 우선, 개미의 최종 x 좌표를 구하는 방법은 다음과 같다.개미가 격자 공간에서 x 좌표의 경계(x=0 or x =w)에 닿는 횟수를 계산한다. c를 그 횟수 라고 할 때 값은 c=(x+t)/w 이며, 시간이 지난 뒤 개미의 최종 x 좌표 xf는 아래와 같다.
c가 홀수일 때 : xf = w - ( (x + t)mod w) c가 짝수일 때 : xf = (x + t) mod w마찬가지의 방법으로 t 시간이 지난 뒤 개미의 최종 y 좌표를 구할 수 있다