[백준] 22869번: 징검다리 건너기 small (파이썬/Python) - DP

https://www.acmicpc.net/problem/22869

22869번: 징검다리 건너기 (small)

징검다리 건너기 (large) 문제와 거의 동일하게 풀었다. 
다만 마지막에 dp[-1] 칸이 값이 k보다 작거나 같은지 확인해주면 된다. 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
array = list(map(int, input().split()))
INF = int(1e9)
dp = [INF]*n # i 번째까지 올때 드는 최대힘
dp[0] = 0
for i in range(1, n):
    for j in range(0, i):
        cost = max((i-j) * (1+abs(array[i]-array[j])), dp[j]) # i 번째 돌에서 j 번째돌로 이동할 때의 비용
        if cost <= k:
            dp[i] = min(cost, dp[i])

if dp[-1] <= k:
    print("YES")
else:
    print("NO")