[백준] 1446번 지름길 (파이썬)

 

문제

 

1446번: 지름길

 

 

 

정답 소스코드 (Python)

 

n,d=map(int,input().split())
shortcut=[]
for i in range(n):shortcut.append(list(map(int,input().split())))
shortcut.sort()
dp=[i for i in range(d+1)]     

k=0
for i in range(d+1):
    dp[i]=min(dp[i-1]+1,dp[i])
    while k<n:
        if i==shortcut[k][0]:
            if shortcut[k][1]<=d:
                dp[shortcut[k][1]]=min(dp[i]+shortcut[k][2],dp[shortcut[k][1]])
            k+=1
        else:break
    
print(dp[d])

 

 

풀이  (Python)

 

Point 1)  기본 로직

dp배열을 처음부터 고속도로 끝까지 각 거리로 초기화해 준다. 이후 매 반복문마다 전 칸에서 현재 칸으로 왔을 때 더 적은 값을 dp배열에 저장해준다.

dp[i]=min(dp[i-1]+1,dp[i])

 

 

 

지름길이 시작되는 부분을 포인트로 잡고, 해당 포인트에서 시작할 수 있는 지름길이 여러 개 이므로 while문으로 처리를 해주었다.

지름길이 시작되는 점에서 해당 지름길이 고속도로 끝을 넘어가지 않는다면,

도착지점의 dp배열에 지름길을 이용한 dp값과 이용하지 않은 dp값을 비교하여 최솟값을 저장해 준다.

 

 

if i==shortcut[k][0]:
    if shortcut[k][1]<=d:
        dp[shortcut[k][1]]=min(dp[i]+shortcut[k][2],dp[shortcut[k][1]])

 

 

이와 같이 고속도로 끝까지 dp최솟값 비교를 마친 이후에 맨 끝점의 dp값을 출력하면 쉽게 풀이가 가능하다.