DP - 1446번: 지름길

DP로 풀어야 하는 대표적인 문제 경우

• LIS / 증가 수열 - i까지 증가 수열 중 가장 긴 길이
• 배낭 문제 - 무게 w일 때 최대 가치
• 동전 문제 - 금액 x를 만드는 최소 동전 개수
• 최단 경로 (특수) - i까지 오는 최소 비용 (지름길, 포탈 등)
• 게임 / 시뮬레이션 - 현재 상태에서 이길 수 있는가?

from collections import defaultdict

n, d = map(int, input().split())
roots = defaultdict(list)

for _ in range(n):
    line = list(map(int, input().split()))
    # 도착 - 출발 < 길이 (이득X) 이거나 지름길의 도착 지점이 d를 벗어나면 패스 
    if line[1] - line[0] <= line[2] or line[1] > d:
        continue
    roots[line[1]].append((line[0], line[2]))


# 모든 거리를 무한대로 초기화
dp = [float('inf')] * (d + 1)
dp[0] = 0

for i in range(1, d + 1):
    # 지름길 안쓰는 경우
    dp[i] = dp[i - 1] + 1
    # i까지 갈 수 있는 지름길을 쓰는 경우
    for s, c in roots[i]:
        dp[i] = min(dp[i], dp[s] + c) # 기존 거리 vs 지름길 타는 경우 비교해서 최소값으로 갱신

print(dp[d])