문제 개요
각 쿼리가 세 값 [ai, bi, di]로 구성된 쿼리 목록 Q가 주어졌다고 가정해 봅시다. 우리는 좌표 평면 위의 원점 (0, 0)에서 출발하며, 한 번의 걸음으로 현재 위치 (x₁, y₁)에서 새로운 위치 (x₂, y₂)로 이동할 수 있습니다. 단, 이때 두 점 사이의 유클리드 거리는 반드시 a 이상, b 이하여야 합니다.
목표는 각 쿼리마다 원점 (0, 0)에서 목적지 (di, 0)까지 도달하는 데 필요한 최소 걸음 수를 구하는 것입니다.
예시
입력이 Q = [(2,3,1), (1,2,0), (3,4,11)]일 때 출력은 [2, 0, 3]입니다.
- 첫 번째 쿼리 (a=2, b=3, d=1): (0, 0)에서 (½, √15⁄2)로 이동한 뒤 다시 (1, 0)으로 이동하면 됩니다. 각 걸음의 길이는 정확히 2이므로 조건을 만족하며, 총 2걸음이 필요합니다.
- 두 번째 쿼리 (a=1, b=2, d=0): d가 0이므로 이미 목적지에 있는 상태입니다. 이동할 필요가 없으므로 출력은 0입니다.
- 세 번째 쿼리 (a=3, b=4, d=11): (0, 0) → (4, 0) → (8, 0) → (11, 0) 순서로 이동하면 각 걸음의 길이가 4, 4, 3으로 모두 [3, 4] 범위 안에 들어갑니다. 따라서 3걸음이면 충분합니다.
접근 방법
이 문제는 그리디(Greedy) 방식으로 해결할 수 있습니다. 함수 steps(a, b, d)를 정의하고 다음 규칙에 따라 답을 계산합니다.
- mmin := min(a, b), mmax := max(a, b)로 설정합니다.
- d가 0이면 이미 목적지에 도달한 것이므로 0을 반환합니다.
- d가 mmin 또는 mmax와 같으면 한 걸음으로 정확히 도달할 수 있으므로 1을 반환합니다.
- d가 mmax보다 작으면 두 걸음이면 반드시 도달할 수 있습니다. 첫 걸음과 두 번째 걸음의 길이를 적절히 조절해 삼각형을 이루도록 이동하면 되기 때문입니다. 이 경우 2를 반환합니다.
- 그 외의 경우(d > mmax)에는 매 걸음을 최대한 크게 밟는 것이 유리합니다. 한 걸음당 최대 mmax만큼 이동할 수 있으므로 ⌈d / mmax⌉(올림값)을 반환합니다.
메인 루틴에서는 각 쿼리에 대해 steps() 함수를 호출하고, 그 결과를 리스트에 모아 반환하면 됩니다.
파이썬 구현 예제
from math import ceil
def steps(a, b, d):
mmin = min(a, b)
mmax = max(a, b)
if d == 0:
return 0
if d in (mmin, mmax):
return 1
if d < mmax:
return 2
return ceil(d / mmax)
def solve(Q):
res = []
for q in Q:
a, b, d = q
res.append(steps(a, b, d))
return res
Q = [(2, 3, 1), (1, 2, 0), (3, 4, 11)]
print(solve(Q))
입력
[(2, 3, 1), (1, 2, 0), (3, 4, 11)]
출력
[2, 0, 3]
정리
핵심은 목적지까지의 거리 d를 기준으로 세 가지 경우로 나누어 생각하는 것입니다. d가 허용 보폭 범위 안에 있으면 1걸음, 최대 보폭보다 가까우면 2걸음, 그보다 멀면 최대 보폭으로 나눈 올림 값이 곧 최소 걸음 수가 됩니다. 이 방식은 각 쿼리를 O(1) 시간에 처리할 수 있어 쿼리 개수가 많아도 매우 효율적으로 동작합니다.