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

지름길이 있는 고속도로에서 목적지까지 가장 빠르게 가는 방법을 연구하는 문제이다. 역주행은 불가능하다.

Python

시도 1 - 함수

import sys

sys.setrecursionlimit(10 ** 6)

n, d = map(int, input().split())

# 거리 저장할 리스트 초기화
memo = [-1 for _ in range(d+1)]

# 도착지 기준 시작점과 거리 저장
road = {}
for _ in range(n):
  start, end, dist = map(int, input().split())
  
  # 고속도로 벗어나는 end는 생략
  if end > d:
    continue

  if end in road:
    road[end].append((dist, start))
  else:
    road[end] = [(dist, start)]
    

memo[0] = 0

# x만큼 가려면 얼마나 걸리는지 계산
def drive(x):
  # memo에서 안 구해졌을 경우
  if memo[x] == -1:
    # 혹시 지름길 도착지 있으면 그거 고려해서 다시 계산하기
    newMin = d
    if x in road:
      for dist, s in road[x]:
        # s까지 운전한 거리 + 지름길 길이 vs 이때까지 구한 min
        newMin = min(drive(s) + dist, newMin)
    # 새로 구한 거리 vs 바로 전칸에서 온 거리
    memo[x] = min(drive(x-1) + 1, newMin)
  return memo[x]

print(drive(d))

메모이제이션과 재귀함수를 통해서 답을 구했다. d부터 거꾸로 접근하면서 만약에 지름길이 있다면 각 지름길별로 거리가 어떻게 되는지 반영해서 최소값을 dp에 저장했다.

시도 2 - for

from collections import defaultdict

n, d = map(int, input().split())

short = defaultdict(list)

for _ in range(n):
  start, end, length = map(int, input().split())
  
  short[end].append((start, length))
  

dp = [10000 * n * d] * (d+1)
dp[0] = 0

# 점화식
# dp[n] = min(dp[n-1] + 1, short[n][1] + dp[short[n][0]])
for i in range(1, d+1):
  dp[i] = dp[i-1] + 1
  
  for start, cost in short[i]:
    dp[i] = min(dp[i], cost + dp[start])
      
  
print(dp[-1])

0부터 d까지 올라가면서 접근했다. short에 지름길의 도착점을 key로해서 시작점과 거리를 저장했다. 그리고 올라가면서 기본적으로는 dp[i] = dp[i-1]을 계산했지만, 만약 지름길이 있다면 지름길로 가는 거리를 비교해서 저장했다.