[백준/10158] 개미 | 점화식 그게 뭔데 그거 어떻게 하는 건데

10158 개미

 

알고리즘

t의 범위가 1 ≤ t ≤ 200,000,000이므로 완전탐색을하면 타임아웃이다.

그렇다면 어떤 점화식을 세워서 문제를 풀어야 한다는 건데

 

1. x와 y의 독립성

이 문제는 1초의 시간이 지날 때

x = (x+1) or (x-1)이 되고

y = (y+1) or (y-1)이 된다.

따라서 각각의 값이 독립적으로 움직인다는 결론에 도달할 수 있다. 

 

2. 이동 횟수와 이동 거리의 관계

 

x좌표와 y좌표는 각각 t만큼 이동을 하게 되고, 이 이동 주기가 2*w, 2*h이다.

아래와 같은 그래프를 보면 이해가 쉽다.

https://kthng.tistory.com/29

따라서 이동 자체에 대한 점화식은 다음과 같다.

• (p+t) % 2*w
• (q+t) % 2*h

이제 이동 좌표에 관한 점화식을 얻었으니, 거리를 구하면 된다.

 

거리는 수학적으로 뺄셈을 의미하기도 한다. 거리는 일반적으로 두 개체 사이의 공간상의 차이를 의미하기 때문이다.

여기서 문제는 벽면에 부딪힐 때마다 방향을 전환해야 한다는 것이다. 벽면에 부딪힐 때마다 방향을 전환하는 것에 대한 점화식은 다음과 같다.

 

• w - abs(w - (p+t)%(2*w))
• h - abs(h - (q+t)%(2*h))

현재 위치에서 다음 순간까지의 거리를 구해주는 것이다. 이때 방향 전환이 각 좌표에 -1, +1 하는 형식이므로 절댓값을 씌워준다.

전체 코드

import sys; input=sys.stdin.readline

w,h=map(int, input().split())
p,q=map(int, input().split())
t=int(input())

# 각각의 축의 이동 거리 점화식
x= w - abs(w - (p+t)%(2*w))
y= h - abs(h - (q+t)%(2*h))

print(x, y)

알게된 점

• 답이 쉽게 안보이면 점화식을 구해보자. 
• 점화식을 세우려면 일단 단계별로 or 번호 순으로 아이디어를 정리해보자. 훨씬 일반화가 수월하다.
• 이런 문제를 접하자마자 아이디어를 떠올린다는 건 쉽지않다. 많은 문제를 풀어보면서 노련함을 쌓는게 중요하다고 느껴진다.