[백준] 10158 - 개미 (Python)

문제 링크

알고리즘

• 수학

풀이

t (시간)의 범위가 1 ~ 200,000,000 이므로 시뮬레이션을 돌리면 무조건 시간초과가 난다.
따라서 다른 방식으로 풀어야 한다.

1초의 시간이 지나면 개미의 x값은 (x+1) 아니면 (x-1) 이되고
y값도 마찬가지로 (y+1) or (y-1) 이 된다.

x값과 y값을 따로 구해서 풀었다.

개미가 처음 위치한 곳이 아래 그림처럼 (p,q) 에 주어진다. (4,1)

먼저 처음의 위치 (p,q) 에서 시간을 더한 값을 격자 (w,h)의 길이로 나눈 나머지를 구한다.

나머지가 0이 아니면 그 값을 끝 (w,h) 에서 뺀다.
하지만 나머지가 딱 나누어 떨어지면 0에서 더해준다.

예를 들면 위의 그림에서 개미가 8초 후에 있을 곳은 x = 0, y = 1 이다.
먼저 x값을 구하려면 초기값 (4) 에서 시간 (8) 을 더한 값 (12) 에서 격자의 가로길이 (6) 으로 나눈 나머지 (0) 을 구한다. 원래는 격자의 오른쪽 끝 (6) 에서 나머지 (6) 을 빼야 하지만 6은 나머지로 나올 수 없기 때문에 왼쪽 끝 (0)에서 더해주면 된다.

코드

# 개미

# (w * h 격자)
w, h = map(int, input().split())

# 처음 개미의 위치 (p,q)
p, q = map(int, input().split())

# 개미가 움직인 시간
t = int(input())

# 개미가 이동한 거리 - 왕복한 거리
a = (p + t) // w
b = (q + t) // h

if a % 2 == 0:
    x = (p + t) % w
else:
    x = w - (p + t) % w

if b % 2 == 0:
    y = (q + t) % h
else:
    y = h - (q + t) % h

print(x, y)