[Baekjoon][Python] 1446번 지름길

1446번 지름길

문제

풀이

해당 문제는 다이내믹 프로그래밍을 이용해야 한다.
D까지 for문을 돌면서, 현재시점에서의 최소 거리를 구해가면 된다.
현재까지의 최소 거리와 현재까지 오는 지름길이 존재한다면, 그 둘을 비교해 작은 것을 고르면 된다.
실버1 문제이지만 생각보다 간단한 문제이다.
나는 중간 for문의 불필요한 부분을 탐색하는 것을 없애려고 정렬을 한뒤 조건문을 하나 더 넣어주었다.
코드는 다음과 같다.

import sys

input = sys.stdin.readline

N, D = map(int, input().split())

short = []
dp = [0]

for _ in range(N):
    start, end, length = map(int, input().split())
    short.append([start, end, length])
short.sort(key=lambda x: x[1])

for i in range(1, D + 1):
    dp.append(dp[i - 1] + 1)
    for j in range(N):
        if short[j][1] > i:
            break
        elif short[j][1] == i:
            dp[i] = min(dp[i], dp[short[j][0]] + short[j][2])

print(dp[-1])