[백준] 10158_개미

📕 문제

가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.

위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매 시간마다 (6,4), (5,3), (4,2), (3,1)로 움직인다. 

여러분은 크기 w×h인 격자 공간에서 처음에 (p,q)에서 출발하는 개미의 t시간 후의 위치 (x,y)를 계산하여 출력해야 한다. 개미는 절대 지치지 않고 같은 속력으로 이동한다고 가정한다. 

문제에서 w와 h는 자연수이며 범위는 2 ≤ w,h ≤ 40,000이다. 그리고 개미의 초기 위치 p와 q도 자연수이며 범위는 각각 0 < p < w과 0 < q < h이다. 그리고 계산할 시간 t의 범위는 1 ≤ t ≤ 200,000,000이다.

 

[입력]

첫줄에는 w와 h가 공백을 사이에 두고 주어진다. 그 다음 줄에는 초기 위치의 좌표값 p와 q가 공백을 사이에 두고 주어진다. 3번째 줄에는 개미가 움직일 시간 t가 주어진다. 

 

[출력]

출력은 t 시간 후에 개미의 위치 좌표 (x,y)의 값 x와 y를 공백을 사이에 두고 출력한다. 

 

💡 풀이법

1. 개미가 가는 좌표를 하나하나 적어가다 보면 개미의 x좌표와 y좌표가 주기를 갖는다는것을 알 수 있다.

(x는 2w, y는 2h의 사이클을 가짐)

2. t가 심각하게 크기때문에,,, t를 이 주기로 나눈 나머지로 따로 구한다.

( x와 y의 주기가 다르기 때문에 tx, ty를 따로 구해줘야함)

3. x와 y는 1씩 커지다가 경계(w, h)를 만나면 1씩 줄어들고 다시 경계(0)을 만나면 다시 1씩 커지는 양상을 보이기 때문에 각자의 시간만큼의 for문을 돌리며 x와 y를 변화시켜준다.

 

w, h = map(int, input().split())
x, y = map(int, input().split())
t = int(input())

tx = t % (2*w)
ty = t % (2*h)

temp = True
for _ in range(tx):
    if x == w:
        temp = False
    elif x == 0:
        temp = True
    if temp: x += 1
    else: x -= 1

temp = True
for _ in range(ty):
    if y == h:
        temp = False
    elif y == 0:
        temp = True
    if temp: y += 1
    else: y -= 1

print(x, y)

-> 처음에는 한칸씩 옮기는 코드를 짰는데 시간초과가 나서 봤더니 시간 제한이 0.15초.. 심지어 t는 2억까지;;

바로 규칙을 찾아서 다시 짰다.. 휴