[BOJ/py] 1446 지름길

문제 링크 https://www.acmicpc.net/problem/1446

📝 문제

문제 설명

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

💻 코드

N, D = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

dp = [i for i in range(D+1)]

for i in range(D+1):
    if i > 0:
        dp[i] = min(dp[i], dp[i-1]+1)

    for s, e, l in arr:
        if i == s and e <= D and dp[i] + l < dp[e]:
            dp[e] = dp[i] + l

print(dp[D])

📌 해결방법

1. 0 부터 D까지의 최단거리 테이블 생성
2. dp[i]와 dp[i-1]+1 값을 비교하여, 더 작은 값을 현재 값으로 설정
3. 만약 현재 위치에 지름길 존재한다면, 지름길로 건너간 곳의 원래 값과 지름길로 건너기 전의 값 + 지름길의 거리 중 더 작은 값으로 건너간 곳의 값을 변경