제31회 한국정보올림피아드 시/도 지역 본선 (2014.5.24) 초등부 문제 3,중등 2 koi_ant

문제는 더블릿 옥상에 있는 koi_ant입니다.

문제 사이트 주소입니다.

http://183.106.113.109/pool/koi_ant/koi_ant.php?pname=koi_ant

공간안에 개미가 있고 대각선으로만 몇 번 움직일 수 있을 때 다 움직이고 난 후 개미의 좌표를 구하는 문제입니다.

if와 for를 통해 개미의 움직임을 하나씩 따라가고 t번 움직인 후의 좌표를 구하는 방법은 t가 커짐에 따라 시간 초과가 뜹니다.

공간 안을 계속 움직일 경우 항상 같은 곳으로 올 때가 있는데 이 경우를 제외하더라도 문제를 해결할 수는 없습니다.

개미가 움직인 좌표를 찾아내는 공식을 도출해야합니다.

1차원적으로 봤을때 w칸을 움직일 수 있는 공간에서, 개미가 현재 좌표 p에서 t번 움직였을 때의 위치는 (p+t)%w로 구해집니다.  예를 들어 w가 4 p가 2 t가 9이면 (2+9)%4의 결과인 3이 개미의 위치입니다.    이를 x, y좌표에 대해 구해주면 됩니다.  그런데 3의 위치는 상대적인 위치로 p, t, w가 각각 3, 5, 6인 경우의 예를 보면 (3+5)%6=2로 2의 위치가 나오지만 실제로는 4가 정답이 됩니다.  이는 오른쪽에서 봣을 때 2번째 위치라는 것을 말합니다.  

개미가 마지막에 오른쪽에서 왼쪽으로 움직이는 것인지, 왼쪽에서 오른쪽으로 움직이는 것인지를 찾아야 하는데 이는 (p+t)/w의 결과가 홀수인지 짝수인지에 의해서 결정됩니다.

개미가 처음에 오른쪽으로 움직이기 때문에 홀수인 경우에는 마지막으로 오른쪽 벽에 튀겼다는 것이고 짝수인 경우에는 오른쪽 한번, 왼쪽 한번씩 튕기고 마지막에 오른쪽으로 가고 있다는 것을 뜻합니다.   이를 이용해 마지막 방향을 구해서 결과 x, y좌표를 이용해줍니다.