16568번 엔비스카의 영혼

문제풀이

기본적인 동적 프로그래밍 문제들과 크게 다르지 않다.

이 문제 또한 여러 조건들을 가지고 진행되게 되는데,

• 기다리기
• a명 앞으로 가기 (앞에 최소 a명 있을 때)
• b명 앞으로 가기 (앞에 최소 b명 있을 때

이 3가지 조건들을 충족하면서 계산을 진행해야한다.

예를 들어서 N으로 값이 4가 들어오고 a와 b의 값이 1과 2라고 하면, for문으로 진행될때

i == 1일 경우에는 i에 a와 b의 값을 빼서 넘어 갈 수 없기 때문에 둘다 되는 경우가 없다.

i == 2일 경우 i에 a와 b 값중 a의 값이 i-a-1의 식을 진행하여도 값이 0 이거나 이상의 값을 가지기 때문에 최소 시간으로 저장됨

i == 3일 경우 i에 a와 b의 값중 a도 조건이 가능해서 계산이 가능하지만 이왕이면 더 큰값으로 먼저 거리를 좁히는 것이 더 빠른 시간을 얻을 수 있기 때문에 b로 계산하여 최소 시간을 저장한다.

i == 4일 경우 i에 a와 b의 값중 b의 값으로 계산 할 경우 남은 사람이 0명이 되므로 최종 시간은 2초가 걸린다.

 

코드

import sys
N, a, b = map(int, sys.stdin.readline().split())
arr = [0 for _ in range(1000001)]
for i in range(1, N+1):
    arr[i] = arr[i-1] + 1
    if i-a-1 >= 0: arr[i] = min(arr[i], arr[i-a-1] + 1)
    if i-b-1 >= 0: arr[i] = min(arr[i], arr[i-b-1] + 1)
print(arr[N])