[백준/Python] 1446번 지름길 풀이

1. 문제해석

 

---

2. 풀이 과정

문제 알고리즘 선택

• 지름길을 타지 않았을 때 이전 값과 지름길을 탄 경우의 값을 비교하는 형태로 이전 값에서 다음 값을 쌓아올리기 가능
• 최대 거리가 1만이며 최대 지름길의 경우의 수가 12개로 모든 경우의 수를 dp로 제한 시간 내에 해결 할 수 있다.
• dp로 풀이

풀이 과정

1. 현재 값에서 지름길을 탈 수 있다면 현재 거리에서 지름길을 탄 값과 지름길을 타고 난 후 값을 비교하여 최소값을 넣는다
2. 현재 값과 바로 직전 값에 + 1을 한 값의 최소값을 비교한다.

---

3. 코드

import sys
route, distance = map(int, sys.stdin.readline().split())
shortPath = [list(map(int, sys.stdin.readline().split())) for _ in range(route)]

answer = [val for val in range(distance + 1)]

for d in range(distance + 1):
    if d > 0:
        answer[d] = min(answer[d], answer[d - 1] + 1)
    for sp, ep, dist in shortPath:
        if sp != d or ep > distance:
            continue
        answer[ep] = min(answer[ep], answer[d] + dist)

print(answer[-1])

2024년 3월 9일 (dp)

관련링크: https://www.acmicpc.net/problem/1446

1446번: 지름길

느낀점: 쉬운 dp 문제는 푸는데 시간도 많이 걸리지 않는 것 같다