백준 1446 파이썬 코드 답안

문제

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

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

입력

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

출력

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

문제 풀이

처음 접근한 방식은 거리를 기록할 리스트를 만들고, 지름길에 대한 정보를 먼저 해당 리스트에 업데이트 하는 방향으로 접근을 했다. 예를 들어서 1,2,3,4,5, .... , 147,148,149,150 순으로 기록이 된 리스트를 먼저 만들었다. 그리고 0 50 10을 업데이트 하면, d[50] = 10이 되고, d[100] = 10 + 10 = 20이 되는 식으로 업데이트를 했다.

지름길을 다 업데이트하고 난 후로는, d라는 리스트에 대해서 처음부터 끝까지 한칸 한칸씩 점검하는 방식으로 갔다. 예를 들어서 d[50]라는 곳에 들릴 때는, d[50]가 현재 가지고 있는 값(예를 들어 지름길로 먼저 왔다면, d[50]의 값이 차례차례 온 것보다 더 작을 수 있기 때문에 d[50] = min(d[49] + 1, d[50])의 값을 기입하는 방식으로 했다.

이 경우 문제가 있었는데, 지름길끼리 맞물리면 상관이 없으나 지름길끼리 다를 경우에는 원하는 값이 나오지 않았다. 예를 들어 지름길이 2개가 나온다고 했을 때 a<b < x < y인 경우, a < x < y < b인 경우가 있을텐데, 내가 짠 코드로는 두 가지 경우 중 하나를 만족할 수 없었다.

예를 들어 d[50]을 볼 때, d[50]이 50이 아니라고 한다면, 이 때의 d[50]과 50의 차이, d[49]+1과 50의 차이를 비교해서 뭔가 업데이트 해주는 식으로 접근을 하려고 했는데, 엑셀로 하나하나 표현해본 결과 절대로 발라낼 수 없는 경우가 있다는 것을 알게 되었다.

그래서 지름길이 하나 들어올 때마다, 최소값을 전체적으로 업데이트 해주는 식으로 코드를 짰다.  b는 지름길의 종착지인데, b가 D보다 클 경우 Index Error가 발생하기 때문에 b가 D보다 작을 경우에만 실행하도록 처리해주었다. 그리고 b의 값이 업데이트 된 후부터는 b부터 D까지 1칸씩 전진해가면서 최소값을 업데이트 해주는 방식으로 진행했다. 

 

import sys
N,D = map(int,sys.stdin.readline().split())
my_list = []
for i in range(N) :
    my_list.append(list(map(int,sys.stdin.readline().split())))
my_list = sorted(my_list,key = lambda x : (x[0],x[1],x[2]))
d = [i for i in range(D+1)]


for i in my_list :
    a,b,c = i
    if b <= D :
        d[b] = min(d[a] + c,d[b])
    for kk in range(a,D+1) :
        d[kk] = min(d[kk-1] + 1 , d[kk])



print(d[D])