[Python/코테] 백준 10158 개미

10158 개미

문제 및 조건 설명: https://www.acmicpc.net/problem/10158

알고리즘 설계

💡idea.

결국 반사된다는 조건도, 특정 좌표로 한 번 이동한다는 의미이다. 몇 가지 경우를 나눠서 t번 반복하는 방법으로는, 시간 초과 판정을 받게 될 것이다.

몇 가지 조건에 따라 수행해야 하는 연산이 동일하므로 수학식(점화식)을 찾아 반복하면 된다.

 

기존 위치에 따라 (x+1, y+1)로 이동할지, (x-1, y+1) 또는 (x+1, y-1) 등의 다른 좌표로 이동할지가 정해지는 셈이다. 경우를 나누기 복잡하지만, 결국 x좌표와 y좌표를 따로 생각하면 적용되는 연산은 +1 혹은 -1 뿐이다. 

결국, t시간 후 x좌표는 초기 좌표 p에서부터 np로 변한다고 가정했을 때 0 ≤ np ≤ w 이다.

 

🎲step.

1. x좌표(y좌표)는 대각선으로만 이동하여, 가능한 연산은 +1 과 -1 뿐이다. 

2. t시간 후 좌표의 위치는 w로 나눈 나머지 값이다. 이 때, 증가(+)방향인지, 감소(-)방향인지만 알면 정확한 좌표도 구할 수 있게 된다.

3. 방향을 파악하기 위해서는 (최초 위치 + t) // w 가 짝수(0에서 w방향으로, 증가)인지 홀수(w에서 0방향으로, 감소)인지 계산하면 된다.

 

알고리즘 구현

코드 출처: https://woojinhong.tistory.com/m/124

w, h = map(int, input().split())
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)

나다어

• 나뉘는 케이스별로 공통점을 찾아보고, 더 단순한 경우로 나눌 수 없을까 고민해보기!
  ex) 각 경계에 부딪혀서 반사되는 경우 4가지 * t번 반복 → X좌표와 Y좌표의 움직임 각각 2가지 * t번 반복