백준_16568_엔비스카의 영혼 (python)

(python 풀이가 하나도 존재하지 않아서 이 글을 써 봅니다.)

 

★ 접근

기다리기, a만큼 새치기, b만큼 새치기 3가지 경우를 혼합하여 최소한의 횟수로 앞으로 가야하는 상황입니다. 보통 이 상황에서 bfs를 떠올립니다. 필자도 bfs를 떠올렸지만 n의 최대 크기 때문에 불안한 감이 있었습니다. 역시나 시간 초과가 나왔고 dp로 풀기로 했습니다.

 

★ 풀이

(1로 만들기 문제와 다른 점이 하나 없습니다.)

1. 1,a+1, b+1을 0보다 크거나 같은 상황에서 빼면서 최소값을 구해나가면 된다. 

 

★ 코드

from collections import deque
import sys
input = sys.stdin.readline
n,a,b = map(int,input().split())
dp = [float("inf")] * 1000001
dp[n] = 0
for i in range(n,-1,-1):
    if i-1 >= 0: dp[i-1] = min(dp[i-1], dp[i] + 1)
    if i-a-1 >= 0: dp[i-a-1] = min(dp[i-a-1], dp[i] + 1)
    if i-b-1 >= 0: dp[i-b-1] = min(dp[i-b-1], dp[i] + 1) 
print(dp[0])

★ 회고

 python으로 ps를 해내고 싶다.