백준[JS] > 1446번 지름길

문제링크

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

문제풀이

DP로 연산횟수를 최적화하여 풀 수 있다. dp[1]은 1의 거리를 갔을 때 최소거리를 의미하며 순서대로 dp[1], dp[2], dp[3] ... 채워가면서 마지막에 dp[D]를 구할 수 있다.

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let [N, D] = input
    .shift()
    .split(" ")
    .map((n) => Number(n));

let dp = Array(D + 1).fill(0);

let shortcut = input.map((str) => {
    return str.split(" ").map((n) => Number(n));
});

shortcut.sort((a, b) => {
    if (b[1] !== a[1]) {
        return a[1] - b[1];
    } else {
        return a[2] - b[2];
    }
});

for (let i = 1; i <= D; ++i) {
    dp[i] = dp[i - 1] + 1;

    for (let j = 0; j < N; ++j) {
        let [start, end, length] = shortcut[j];
        if (end === i) {
            dp[i] = Math.min(dp[i], dp[start] + length);
        }
    }
}

console.log(dp[D]);