[백준] 1446. 지름길

1446. 지름길

 

• 내 풀이
  • O(D + N)이라 완탐했음
  • DFS + DP
  • dp[i]: 0에서 i까지 도달하는 데 필요한 최소 거리
  • 현재 위치에서 갈 수 있는 지름길 or 직진을 따라가며 최소 거리 갱신

from collections import defaultdict

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

road=defaultdict(list)
for _ in range(n):
    s,e,k=map(int,input().split())

    road[s].append((e,k))

dp=[i for i in range(d+1)]
def dfs(end,total):
    if end>d:
        return
    if dp[end]<total:
        return
    else:
        dp[end]=total

    for nxt in road[end]:
        dfs(nxt[0],total+nxt[1])
    dfs(end+1,total+1)

dfs(0,0)
print(dp[d])

 

 

• 다른 풀이- DP + 선형 탐색 (Bottom-Up 방식)
  • DFS 호출 없음 (스택 깊이 문제 X)
  • dp[i]를 매 순간 최적으로 갱신
  • 순차 탐색으로 효율적인 메모리 사용

from collections import defaultdict

n, d = map(int, input().split())
shortcuts = defaultdict(list)

for _ in range(n):
    s, e, l = map(int, input().split())
    if e <= d and e - s > l:  # 지름길이 유의미할 때만
        shortcuts[s].append((e, l))

dp = [float('inf')] * (d + 1)
dp[0] = 0

for i in range(d + 1):
    if i > 0:
        dp[i] = min(dp[i], dp[i - 1] + 1)
    for e, l in shortcuts[i]:
        if dp[e] > dp[i] + l:
            dp[e] = dp[i] + l

print(dp[d])