[백준/파이썬] 1446 지름길

#문제링크

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

1446번: 지름길

#나의풀이

import sys

if __name__=="__main__":
    N, D = map(int, sys.stdin.readline().split())
    arr = [[] for _ in range(10001)]
    for _ in range(N):
        start, end, express = map(int, sys.stdin.readline().split())
        arr[start].append([end, express])
    distance = [i for i in range(D+1)]

    for i in range(D+1):
        if i != 0:
            distance[i] = min(distance[i], distance[i-1]+1)
        for end, express in arr[i]:
            if end <= D and distance[end] > express + distance[i]:
                distance[end] = express + distance[i]

    print(distance[D])

#해설

다익스트라 문제로 구분되서 풀었는데 단순 dp로도 풀리는거 같다.

 

    arr = [[] for _ in range(10001)]
    for _ in range(N):
        start, end, express = map(int, sys.stdin.readline().split())
        arr[start].append([end, express])
    distance = [i for i in range(D+1)]

arr에 index가 시작위치가 되고 배열에 끝나는 지점과 지름길 길이가 저장된다.

distance는 dp가 될것이고 D의 길이만큼 생성해주었다.

 

    for i in range(D+1):
        if i != 0:
            distance[i] = min(distance[i], distance[i-1]+1)
        for end, express in arr[i]:
            if end <= D and distance[end] > express + distance[i]:
                distance[end] = express + distance[i]

    print(distance[D])

i가 0일경우 인덱스 범위를 나가버리므로 0이 아닐때 이전과 비교하여 작은것을 선택한다.

이후 arr[i]에 고속도로가 있다면 끝나는 지점이 D를 넘기지 않는지 확인하고 distance[end]가 지름길+현재거리 보다 작다면 값을 바꿔준다.