[99클럽/파이썬 챌린저/27일차] 지름길

백준 1446번 지름길 S1

 

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

입력
첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

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

다이나믹 프로그래밍, 그래프 이론, 최단 경로, 데이크스트라

 

 

데이터가 적어 다이나믹 프로그래밍으로 풀이하였다.

지름길을 오름차순으로 정렬한 뒤 계산을 시작했다.

 

지름길 시작 위치까지 오는 거리는 min(현재 위치 - 이전 시작위치 + 이전 시작위치 거리)로 볼 수 있다.

해당 결과로 해당 정점까지 오는 거리를 갱신하고, 도착 지점에 대한 거리까지 갱신해 준다.

해당 방식을 모든 지름길에 대해서 진행하였다.

 

마지막 도착 지점까지의 거리도 min(도착 지점 - 마지막 지름길 시작 위치 + 지름길 시작 위치 거리)  위치 <= 도착 지점으로 이전에 썼던 방식을 똑같이 사용하여 구했다

 

import sys

n, d = map(int, sys.stdin.readline().split())

lines = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
lines.sort()

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

last_pos = 0
for s, e, c in lines:
    if c > e-s or e > d: continue
    min_cost = dp[last_pos] + s-last_pos
    for pos in range(last_pos, s+1):
        min_cost = min(s - pos + dp[pos], min_cost)

    dp[s] = min_cost
    dp[e] = min(min_cost + c, dp[e])
    last_pos = s

min_cost = dp[last_pos] + d-last_pos
for pos in range(last_pos, d+1):
    min_cost = min(d - pos + dp[pos], min_cost)
print(min_cost)​

 

---