스타트링크

풀이

 바로 이전에 푼 숨바꼭질과 매우 매우 유사한 문제다. 언뜻 보면 그리디 유형의 문제 같지만 BFS로 모든 경우의 수를 탐색해야 하는 완전 탐색 문제다.

from collections import deque
F, S, G, U, D = map(int, input().split())
visited = [-1] * (F+1)

queue = deque([S])
visited[S] = 0
while queue:
    x = queue.popleft()
    if x == G:
        print(visited[x])
        exit(0)
    if 1<=x+U<=F:
        if visited[x+U] == -1:
            visited[x+U] = visited[x] + 1
            queue.append(x+U)
    if 1<=x-D<=F:
        if visited[x-D] == -1:
            visited[x-D] = visited[x] + 1
            queue.append(x-D)

print("use the stairs")

시간복잡도 : O(F)