개미

문제를 풀어본 후 해설을 보시면 좋습니다 !! ^ㅡ^

예상 난이도 : 5 / 10

이번 문제는 '개미'(https://www.acmicpc.net/problem/10158) 입니다.

이 문제가 좋다고 생각한 이유는 '벡터에 대해서 생각해 볼 수 있으며, 시뮬레이션을 해야 할 것 같지만

일정한 패턴(주기)가 있어서 그렇게 하지 않아도 되는 문제'에 대해서 생각해 볼 수 있기 때문입니다.

코딩 테스트에서 효율성까지 빡빡하게 보는 곳은 많이 없습니다.

하지만 효율성까지 고려해서 짜면 좋겠죠.

그리고 무엇보다 이 문제는 고등학교 수학시간에 배웠던 간단한 벡터의 성질에 대해서 생각해 볼 수 있습니다.

이 개미의 움직임을 하나하나 시뮬레이션을 해보려고 한다면 저같은 경우 골치가 많이 아플 것 같네요.

하지만 X축과 Y축의 움직임을 따로따로 생각해보면 그러지 않아도 될 것 같다는 생각을 하게 됐습니다.

그렇게 보게 되면, X축 이 끝에서 끝으로 이동하고, Y축도 그렇습니다. 벽에 부딪히면 다시 반대편으로 이동하고

이런 움직임의 연속입니다.

입력으로 들어올 수 있는 시간이 무려 200,000,000 입니다. 절대적으로 시뮬레이션으로 하려고 한다면 '1초'라는 

시간 제한 이내에 해낼 수 없습니다.

T = (입력으로 들어온 시간) 이라고 한다면, T / (가로 길이) 와 T / (세로 길이) 이런식으로 계산해 주면 됩니다.

몇 번 왕복했는지에 대한 값이 나오고, %(mod) 연산으로 나머지가 있다면 그것까지 처리해 주면 되겠습니다.

추가) 

조금 더 효율적인 풀이를 배웠습니다.

우선 w, h로 한정된 공간이 아닌 무한한 공간이라고 가정하여 봅시다.

그리고 일단은 T초 후에 (y+T)와 (x+T)에 도달했다고 합니다.

그런 후 Y축만 구해봅시다.

(y+T) % 2*h 이 식을 한 번 볼까요.

왜 2*h로 나눴을까? 이것은 오른쪽 벽에 부딪혀서 반사되는 것을 쉽게 계산하기 위해서 입니다.

int temp = (y+T) % 2*h;
if(temp > h) temp = 2*h - temp;

if문이 참이라면 이 뜻은 벽에 반사된 것을 고려할 것! 이라는 뜻입니다.

따라서 if 문 안의 식으로 처리해주면 됩니다.