[백준 1446] 지름길

문제

 

www.acmicpc.net/problem/1446

1446번: 지름길

 

처음 작성한 코드

import sys

N, D = map(int, sys.stdin.readline().split())
arr = []
for _ in range(N):
    s, e, leng = map(int, sys.stdin.readline().split())
    if e <= D:
        arr.append([s,e,leng])

distance = [i for i in range(D+1)]

for i in range(D+1):
    if i:
        distance[i] = min(distance[i], distance[i-1]+1)
    for j in arr:
        if j[0] == i:
            distance[j[1]] = min(distance[j[0]]+j[2], distance[j[1]])
    print(distance)

print(distance[-1])

1. 입력받을 때 고속도로의 길이(D)보다 지름길 끝 지점(e)이 크면 arr에 추가하지 않았다. -> 빠꾸할 수 없다고 문제에 나와있기때문에 그 지름길을 타봤자 소용이 없음.
2. 고속도로의 길이(D)만큼의 배열을 만들고 그 배열의 값을 갱신시켜주면서 최소 길이를 찾았다. -> 100킬로미터까지의 거리는 distance[100]에 접근하면 구할 수 있도록 만든것.. 마지막 출력값은 고속도로의 마지막까지의 거리를 나타낸다.

깨달은 점

• 너무너무너무 어렵다..  . . . . 언젠간 잘해지겠지..
• 다익스트라는 출발지점에서 도착지까지 최소 거리를 구할 때 사용된다고 한다.. 기억이 하나도 안난다 푸 헹헹..