문제

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

이해

격자상의 개미는 초기에 오른쪽 위 45도로 이동한다. 경계면에 부딪히면 반사되어 다른 방향으로 이동한다.

격자 크기와 개미의 초기 위치, 진행 시간이 주어질 때 개미의 최종 위치를 출력해야 한다.

접근

애드혹 알고리즘이 무엇인지 몰랐는데 단순히 문제 해결을 위한 특정 알고리즘을 사용하는 것이라고 한다. 따라서, 브루트 포스나 그리디 같은 풀이가 애드혹에 포함된다고 할 수 있다.

본 문제에서는 진행 시간 t는 최대 2억까지 가능하다. 따라서, 2억번의 이동을 시뮬레이션하면 불가능할 것이다.

시뮬레이션하지 않고 정답을 구하려면 아무래도 특정 규칙을 찾는 것이 유리해보인다.

(x, y) 움직임을 따로 생각해보면 규칙을 확인할 수 있다. 반사에 대해 생각해보자. 초기에는 오른쪽 위 45도로 움직이기 때문에 (+1, +1)로 이동한다. 계속 이동하다가 벽에 부딪히면 어떤 축의 벽에 부딪혔는지에 따라 움직임이 달라진다. 만일 x축에 부딪혔으면 다음 y좌표를 넘어갈 수 없기 때문에 (+1, -1)이 된다. 반대로, y축에 부딪혔으면 다음 x좌표로 넘어갈 수 없기 때문에 (-1, +1)이 된다.

위에서 알 수 있듯이 x와 y좌표는 따로 판단할 수 있다. 또한, 반사되어 반대쪽으로 이동하기 때문에 초기 위치로 돌아오려면 x의 경우 2 x w, y의 경우 2 x h만큼 이동하면 되는 것이다.

이를 활용하여 t만큼 이동할 때 주기만큼 빼면 나머지로 남는 값을 계산하면 최종 x, y를 구할 수 있다. (2xw, 2xh)만큼 반복됐기 때문에 나머지만 계산하면 된다.

풀이

        int remainW = (t + p) % (2 * w);
        int remainH = (t + q) % (2 * h);

        if (remainW > w) {
            remainW = 2 * w - remainW;
        }
        if (remainH > h) {
            remainH = 2 * h - remainH;
        }

코드는 간단하게 구현할 수 있다. 초기 위치와 t를 더해 주기에 대해서 나머지를 계산한다. 만일 나머지 값이 경계보다 크면 반사되는 것까지 계산해서 값을 처리하면 된다.

결과

나머지 값을 계산할 때 초기위치를 미리 더하지 않아서 틀렸었다. 초기위치까지 나머지 계산에 포함해주자.