1. 문제해석
2. 풀이 과정
문제 알고리즘 선택
- 지름길을 타지 않았을 때 이전 값과 지름길을 탄 경우의 값을 비교하는 형태로 이전 값에서 다음 값을 쌓아올리기 가능
- 최대 거리가 1만이며 최대 지름길의 경우의 수가 12개로 모든 경우의 수를 dp로 제한 시간 내에 해결 할 수 있다.
- dp로 풀이
풀이 과정
- 현재 값에서 지름길을 탈 수 있다면 현재 거리에서 지름길을 탄 값과 지름길을 타고 난 후 값을 비교하여 최소값을 넣는다
- 현재 값과 바로 직전 값에 + 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
느낀점: 쉬운 dp 문제는 푸는데 시간도 많이 걸리지 않는 것 같다
'Problem Solving > 백준' 카테고리의 다른 글
[백준/Python] 16639번 괄호 추가하기3 풀이 (0) | 2024.03.12 |
---|---|
[백준/Python] 16637번 괄호 추가하기 풀이 (0) | 2024.03.12 |
[백준/Python] 1238번 파티 풀이 (0) | 2024.02.29 |
[백준/Python] 2579번 계단 오르기 풀이 (0) | 2024.01.16 |
[백준/C++] 9663번 N-Queen 풀이 (0) | 2024.01.15 |