[BOJ 1446] 지름길

문제

지름길

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

 

 

풀이

설명

운전해야 하는 거리의 최솟값을 구하는 문제입니다.

 

DP를 이용해 해결할 수 있습니다.

 

dp[i]는 i 지점까지 운전해야 하는 거리의 최솟값입니다.

dp[0] = 0으로 초기화합니다.

 

점화식은 다음과 같습니다.

• 고속도로를 따라 이동할 경우
  dp[i] = Math.min(dp[i], dp[i-1] + 1)
• 지름길로 이동할 경우
  도착 지점이 end, 길이를 dist라고 할 때
  dp[end] = Math.min(dp[end], dp[i] + dist)

 

예시 코드

function solution() {
  const [N, D] = input().split(" ").map(Number);
  const dp = Array(D + 1).fill(D);
  dp[0] = 0;
  const graph = Array.from({ length: D + 1 }, () => []);

  for (let i = 0; i < N; i++) {
    const [start, end, dist] = input().split(" ").map(Number);
    if (end <= D) graph[start].push([end, dist]);
  }

  for (let i = 0; i <= D; i++) {
    if (i > 0) dp[i] = Math.min(dp[i], dp[i - 1] + 1);

    for (const [end, dist] of graph[i]) {
      dp[end] = Math.min(dp[end], dp[i] + dist);
    }
  }

  return dp[D];
}