백준 #1446 - [S1] 지름길 : DP

(python3)

1446번: 지름길

 

 

DP로 해결하기

n지점 이하의 dp 배열이 최단으로 저장되어있다는 가정하에, dp[n] = min(dp[n], dp[n-1]+1) 입니다. 바로 앞 지점에서 1만큼 더 이동하거나 이미 지름길로 더 짧게 도달하거나 둘 중 하나입니다.

 

그리고 지름길 시작점이 n 이라면 끝점의 dp 값을 변경해주어야 합니다.

dp[끝점] = min(dp[끝점], dp[시작점]+지름길 길이)

 

앞서서 말한 가정을 성립시키기 위해서는 지름길들이 시작점 기준 오름차순 정렬이 되어있는 상태에서 앞에서부터 하나씩 사용하거나, 매번 지름길 전체를 탐색해서 타겟점 n 을 시작점으로 가진 지름길이 있는지 확인해주어야합니다.

저는 정렬을 해주고 진행했습니다.

 

코드

import sys
def solution(input) :
    N,D = list(map(int,input().split()))
    dp = [10001] * 10001
    dp[0] = 0
    L = [list(map(int,input().split())) for _ in range(N)]
    
    L = sorted(L)

    li = 0
    for t in range(D+1) :
        dp[t] = min(dp[t-1]+1, dp[t])
        while li < N and L[li][0] == t :
            dp[L[li][1]] = min(dp[L[li][1]] , dp[L[li][0]] + L[li][2])
            li+=1
        
    print(dp[D])

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac