[C++] 백준 10158. 개미

https://www.acmicpc.net/problem/10158

10158번: 개미

1. 아이디어

첫 번째로 떠올린 아이디어는 '시뮬레이션'이었습니다.

직접 시뮬레이션을 돌려서 문제를 해보고자했죠.

 

그래서 작성한 코드가 다음과 같습니다.

 

 

말그대로 방향을 바꿔가면서 움직여보는 것이였죠.

시간 제한이 0.15초 이고,

t가 한 없이 커도 w*h 를 간격으로 똑같은 패턴을 보이기 때문에

나머지를 통해 for문을 돌리면 시간초과가 나오지 않을 것이라 생각했습니다.

 

하지만 이는 시간초과입니다.

 

아마도 시뮬레이션으로 풀려면 이보다 더 빠르게는 못풀거라고 생각하는데..

그러면 시뮬레이션이 아닌 다른 방법으로 푸는 것 같습니다.

 

2. 아이디어 2

 

좌표를 x와 y로 나눠봅시다.

그리고 좌표계를 쭉 펼쳐서

전체 크기가 w, h 이 아닌

2*w, 2*h 인 좌표계를 상상해봅시다.

 

개미는 x축과 y축을 독립적으로 봤을 때,

x, y축을 따로따로 왔다갔다 반복운동합니다.

 

즉, 각각 2*w, 2*h의 사이클 주기를 가지고 있습니다.

 

그러므로

x축은 (p + t) % (2*w) 에서

결과 값이 w를 넘었을 경우 2*w에서 해당 좌표를 뺀 값이 정답이고

아니면 그 좌표자체가 정답이라고 여길 수 있습니다.

3. 풀이

 

이렇게 간단한 코드로 해결됩니다.

 

 

생각이 중요한 문제였던것 같습니다.