[백준] 1446 지름길 JavaScript

혅·2024년 11월 27일

백준, 프로그래머스 -JavaScript-

목록 보기

180/215

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

예제 입력

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

예제 출력

내가 했던 풀이 방법

지름길 중에 가능한 지름길만을 possibleShortCut에 저장한다. 불가능한 경우는 D가 end보다 더 멀리 있는 경우이다.
possibleShortCut을 start 기준으로 정렬하고 같을 경우 end를 기준으로 정렬한다.
dp를 D+1 크기의 배열로 선언하고 Infinity로 채워준다. 출발 지점은 0으로 저장한다.
1번 위치부터 D까지 해당 위치까지의 가장 작은 값으로 저장해준다. dp[i] 또는 dp[i-1]+1 중 가장 작은 값이 존재한다. possibleShortCut 중에 start 지점이 현재 위치와 일치하는 경우 해당 지름길을 이용했을 때 도착지점의 최솟값이 dp[i]+length가 더 작다면 dp[end] 값을 바꿔준다. 불필요한 연산을 줄이기 위해 start보다 i가 작다면 반복을 멈춘다.
4번을 반복하다보면 D까지 최솟값이 dp[D]에 저장되게 된다.

코드

const fs = require('fs');
let [n, ...shortCut] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let [N, D] = n.trim().split(' ').map(Number);
let possibleShortCut = [];
for (let i = 0; i < N; i++) {
  let [start, end, length] = shortCut[i].trim().split(' ').map(Number);
  if (end <= D) {
    possibleShortCut.push([start, end, length]);
  }
}

possibleShortCut.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

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

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

  for (const [start, end, length] of possibleShortCut) {
    if (i === start) {
      dp[end] = Math.min(dp[end], dp[i] + length);
    } else if (i < start) {
      break;
    }
  }
}

console.log(dp[D]);