백준 - 1446번(다익스트라, DP)

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

1446번: 지름길

 

import sys

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

for i in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))

arr.sort(key= lambda x:(x[0],x[1],x[2]))

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

for i in arr:
    a,b,c = i
    if b <= d:
        ans[b] = min(ans[a]+c, ans[b])
    for j in range(a,d+1):
        ans[j] = min(ans[j-1]+1, ans[j])

print(ans[d])

 

다익스트라 문제로 분류되어 있지만 다익스트라의 아이디어를 이용한 DP문제라고 생각한다.

ans 배열에는 0부터 종료 지점만큼의 배열이 숫자만큼 담겨 있다.

그리고 주어진 arr을 돌면서 주어진 경로 종료 지점이 최종 목적지보다 작다면 조건문을 실행한다.

시작 지점의  값 + 지름길의 가중치 vs 지름길을 이용하지 않고 주어진 거리만큼 이동

둘 중에서 더 작은 값을 해로 갖는다.

그리고 시작 지점부터 d까지 반복문을 돌면 최단거리로 바뀐 부분부터 기존 값과 비교해서 더 작은 값을

예를 들어 60이던 부분이 지름길로 인해 50이 되면 그다음에는 원래 61이 있었지만

반복문을 통해서 비교해서 50,61,62,63... -> 50,51,52,53... 이렇게 바뀌게 된다. 즉 최단거리가 보장된다.

그럼 최종적으로 종료지점인 ans[d]에 갖고 있는 값이 최단거리가 될 것이다.