b_지름길_1446

문제

b_뱀과 사다리게임_16928 이거랑비슷하다고 생각했다
근데 여기에 이제 가중치가 있는.
그래서 일종의 다익스트라로 생각하였고 되게 복잡하게 풀었다.

다익스트라 형식 풀이

모든 노드를 구했고
예로 0(시작) 10 20 30 50 100(목적지) 까지의 노드가 있다고 치면
각 노드의 차이를 구해서
0 > 10 > 20 >30 > 50 > 100 이렇게 일방향인 노드를 하나 만들어놓고 각노드의 거리 차이를 간선으로 두고 이걸 바탕으로 지름길을 추가하였다.
지금보니 while에 거리짧은거를 선택하는 기법을 쓰지 않았다.

import sys
from collections import deque
import math
import heapq

N,D=map(int,sys.stdin.readline().strip().split())

node = [0]
graph = {}
for _ in range(N):
    s,e,d = map(int,sys.stdin.readline().strip().split())
    if s < 0 or e > D: continue
    graph.setdefault(s,{})
    if e in graph[s]:
        graph[s][e] = min(graph[s][e],d)
    else:
        graph[s][e] = d
    heapq.heappush(node,s)
    heapq.heappush(node,e)
heapq.heappush(node,D)

# <span id="print기본graph"></span>print("기본",graph)


start = 0
dist = {0:0}
while node:
    next = heapq.heappop(node)
    if start != next:
        dist[next] = math.inf
        graph.setdefault(start,{})
        if next in graph[start]:
            graph[start][next] = min(graph[start][next],next-start)
        else:
            graph[start][next] = next-start
        start = next
# <span id="print확장graph"></span>print("확장",graph)
# <span id="print거리dist"></span>print("거리",dist)

start = 0
que = deque([start])
while que:
    tmp = que.popleft()
    if tmp in graph:
        for e in graph[tmp]:
            n_dist = dist[tmp]+graph[tmp][e]
            if dist[e] > n_dist:
                dist[e] = n_dist
                que.append(e)
    # print(tmp,dist)

print(dist[D])

dp 형식의 답

1칸식의 거리를 다돏며 최소한의 거리를 찾는다
실제로 풀면 위의 답같은경우 오류날 확률이 너무 큰거같다. 이게훨씬 나은 것 같다.1

 N, D = map(int, input().split())
ways = [tuple(map(int, input().split())) for _ in range(N)]
 # 끝점 기준으로 정렬
ways.sort()

# <span id="dpi-0에서-i까지의-최소-거리"></span>DP[i] = 0에서 i까지의 최소 거리
dp = [i for i in range(D + 1)]

for i in range(D + 1):
     if i > 0:
         dp[i] = min(dp[i], dp[i - 1] + 1)  # 그냥 1km 이동
     for s, e, l in ways:
        if s == i and e <= D and (e - s) > l:  # 유효한 지름길
             dp[e] = min(dp[e], dp[s] + l)

print(dp[D])