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

Algorithm (PS)

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

minjiwoo 2022. 12. 10. 14:24

728x90

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

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

$N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으

www.acmicpc.net

징검다리 건너기 (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")

728x90