https://www.acmicpc.net/problem/5014
시간 1초, 메모리 256MB
input :
- F, S, G, U, D (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층
output :
- S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력
- 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력
조건 :
- 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동
- U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼(만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)
- 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력
편안....
모든 경우의 수를 확인해서 dp 배열에 저장을 한 후에 마지막에 g 층의 값을 확인하자.
u 버튼을 누르는 경우는 현재 층 + u 한 것이 전체 층 보다 낮을 때 만 가능하며,
d 버튼을 누르는 경우는 현재 층 - d 한 것이 0보다 클 때만 가능하다.
이렇게 모든 경우를 구해서 마지막에 g층을 찾아 갔을 때 -1 이면 엘리베이터로 못 가는 거기 때문에 use the stairs를 출력.
import sys
from _collections import deque
f, s, g, u, d = map(int, sys.stdin.readline().split())
dp = [-1] * (f + 1)
q = deque([])
q.append((s, 0))
while q:
now, button = q.popleft()
if dp[now] != -1:
continue
dp[now] = button
if now + u <= f and dp[now + u] == -1:
q.append((now + u, button + 1))
if now - d > 0 and dp[now - d] == -1:
q.append((now - d, button + 1))
if dp[g] == -1:
print('use the stairs')
else:
print(dp[g])
