[알고리즘풀이 with Python] 백준 1446번 - 지름길

설명 # DP (다이나믹 프로그래밍) : 복잡한 문제를 작은 부분 문제로 나누어 해결하는 방법 지름길의 정보를 입력받습니다. 각 지름길은 시작 위치, 도착 위치, 그리고 길이로 이루어져 있습니다.

지름길의 정보를 시작 위치 기준으로 정렬합니다. 각 지름길에 대해 다음을 수행합니다: 도로의 도착 위치가 고속도로의 끝(D)을 넘어서거나, 지름길의 길이가 실제 거리보다 길면 무시.

그렇지 않으면, 현재 지름길의 시작 위치와 도착 위치를 방문 위치에 추가. 현재 지름길의 시작 위치 이전에, 방문했던 모든 위치의 값을 비교하여, 현재 지름길의 시작 위치까지 가는 거리를 업데이트.

현재 지름길을 따라 도착 위치까지 가는 거리를 업데이트. 현재 지름길의 도착 위치에서 고속도로의 끝(D)까지 가는 거리를 업데이트.

고속도로의 끝까지 가는 최소 거리를 출력합니다. 풀이 import sys input = sys.stdin.readline # N은 지름길의 개수, D는 고속도로의 끝까지의 거리.

N, ...