해결 과정
다익스트라 알고리즘을 활용한 것이 뭐가 있을까 하다가 발견한 문제.
이것 역시 다른 코드를 참고하며 이해했다.
나의 풀이
import sys
N, D = map(int, sys.stdin.readline().split())
graph = []
for i in range(N):
start, end, shortcut = map(int, input().split())
if end <= D: graph.append((start, end, shortcut)) # 거리 넘어가는 건 제외
dis = [i for i in range(D+1)] # [0, 1, 2, 3, ... D]
for i in range(D+1):
dis[i] = min(dis[i], dis[i-1] + 1)
for start, end, shortcut in graph: # 지름길 돌면서 업데이트하기
if start == i:
dis[end] = min(dis[start] + shortcut, dis[end])
print(dis[D])
다른 풀이
IDEA
'Coding Test > 문제 풀이' 카테고리의 다른 글
[문제 풀이] 실패율 (0) | 2022.03.25 |
---|---|
[문제 풀이] 백준 10825 (0) | 2022.03.25 |
[문제 풀이] 백준 18352 (0) | 2022.03.25 |
[문제 풀이] 무지의 먹방 라이브 (0) | 2022.03.24 |
[문제 풀이] 백준 1439 (0) | 2022.03.24 |