매우 큰 수를 나머지 연산으로 줄일 수 있는 마법(백준-개미)

1. 문제

 

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

10158번: 개미

 

좌표평면 안에서 개미가 대각선 방향으로 움직이는데, 벽면에 부딪힐 경우, 반사되어 움직인다.

 

일정한 속력으로 움직일 때, 평면의 크기, 처음 좌표가 주어지고 시간 t가 주어질때, t시간 후에 개미의 위치를 구해본다면..?

 

 

2. 풀이

 

시간 t의 범위가 2억이나 되니까, 일반적인 1칸씩 가는 반복연산으로는 도저히 0.15초만에는 불가능

 

그렇다고 벽면까지 한번에 가는 방법으로 시간을 조금이라도 줄여본다고 해도 도저히 불가능하더라

 

근데 사실 조금만 생각해보면, 대각선으로 움직이기 때문에

 

개미는 결국 x축으로만 보면 좌우로 왔다갔다하고, y축으로만 보면 위아래로 왔다갔다한다는 사실만 파악한다면 아주 쉽게 풀 수 있다

 

예를 들어서 6*4크기의 평면에서 (4,1)에 있는 개미가 8시간 후에 도착하는 점의 좌표는?

 

 

위 그림과 같이 (0,1)에 도착하기는 한데, 좌우와 위아래 관점에서 살펴본다면? 결국 8칸씩 움직인거나 마찬가지다

 

 

따라서, 현재 점의 좌표 (p,q)가 주어지고 크기가 w*h 평면에서 움직인다고 한다면..?

 

t시간만큼 움직인다고 할때..

 

x좌표, y좌표 따로 움직이는 전략을 생각한다

 

그런데 예를 들어서 x=6 에 위치한다고 할때, 남은 거리는 t-(w-p)일텐데, 몇번을 왔다갔다 할 수 있는가??

 

홀수번 왔다갔다한다면? x=0에 존재할거고, 짝수번 왔다갔다한다면? x=6에 존재할거임

 

 

몇번 왔다갔다하는지는 어떻게 알까?? 예를 들어 t=12시간 움직여야 한다고 가정하면.. w=6이니까 2번 움직여야한다.

 

쉽게말해 t를 w로 나눈 몫만큼 왔다갔다 할 수 있다

 

하지만, t를 w로 나눈 몫이 홀수라면, 굳이 왔다갔다 안해도 x=0에 존재하고, 짝수라면 x=w에 존재한다

 

이는 y축으로 움직여도 마찬가지다. t를 h로 나눈 몫이 홀수라면, y=0에 존재하고, 짝수라면 y=h에 존재할거다.

 

그러므로 처음에, (p,q)는 w*h안에 있다는 것은 보장되므로, 만약에 t가 w-p보다 작다면, x축으로 바로 t만큼 움직이지만

 

t가 w-p보다 크다면, 먼저 w-p만큼 움직여서 x=w에 위치시키고

 

남은 t-(w-p)를 w로 나눈 몫을 구해서 이게 짝수면 여전히 x=w에 존재하고, 홀수면 여전히 x=0에 존재할 것이다.

 

그 몫만큼 위치시킨 다음에, t-(w-p)를 w로 나눈 나머지만큼 이동시킨다면, 매우 큰 t에 대해서라도 아주 간단하게 어디에 존재하는지 바로 알 수 있다

 

y축 이동도 마찬가지다. t가 h-q보다 작다면, y축으로 바로 t만큼 이동시키지만

 

크다면 먼저 h-q만큼 움직여서 y=h에 위치시키고 t-(h-q)를 h로 나눈 몫을 구해서 짝수면 y=h에 존재하고, 홀수면 y=0에 존재한다.

 

그 후 t-(h-q)를 h로 나눈 나머지만큼 이동시키면 매우 큰 t에 대해서 바로 어디에 존재하는지 알 수 있다

 

from sys import stdin

w,h = map(int,stdin.readline().split())

p,q = map(int,stdin.readline().split())

t = int(stdin.readline())

x_t = t
y_t = t

if w-p > x_t:
    
    p = p+x_t

else:
    
    x_t -= w-p

    if (x_t//w) % 2 == 0:

        p = w-(x_t%w)

    else:

        p = x_t%w

if h-q > y_t:
    
    q = q+y_t

else:
    
    y_t -= h-q

    if (y_t//h) % 2 == 0:
        
        q = h-(y_t%h)
    
    else:
        
        q = y_t%h

print(p,q)

 

3. 되돌아보기

 

힌트를 좀 보긴했지만.. 그래도 비밀을 잘 파악하고 구현을 잘 했다..

 

항상 수학적으로도 잘 생각해보고 매우 큰 수에 대해서는 혹시나 나머지 연산을 고민해보면 좋을 것 같다