[JavaScript] 백준 1446번: 지름길 (DP)

난이도 : 실버 1
문제 유형 : 다이나믹 프로그래밍
문제 링크 : https://www.acmicpc.net/problem/1446

 

 

문제 풀이

• 메인 생각 : DP를 이용해 각 위치까지 걸리는 시간을 구한다.

처음에는 지름길을 통하여 이동한 위치와 기존에 걸리는 시간들을 비교해야겠다고 생각했다.

그러면 걸리는 시간들을 저장할 array가 필요하고 이전 위치의 시간과 이후 위치의 시간이 연관이 있으므로 다이나믹 프로그래밍을 떠올렸다.

 

먼저 시작지점인 0부터 도착지점인 D까지 반복문을 돌면서 다음 위치에 들어갈 값들을 저장한다.

각 반복마다 다음 지점의 시간을 저장해준다.

또한 현재 지점에서 시작하는 지름길이 있다면 그 지름길을 통한 도착 지점의 값을 갱신해준다.

 

현재 지점이 0이고 지름길이 [0, 50, 10]과 같이 있다면,다음 지점인 1에 현재 지점까지의 시간 + 1을 저장한다. // dp[1] = dp[0] + 1;
그리고 지름길의 정보를 갱신해준다. // dp[50] = dp[0] + 10;

지금의 경우 다른 지름길이 없다는 가정이지만 실제로는 다음 지점에 지름길을 통하여 이미 적은 값이 저장되어 있을 수 있으므로 도착 지점에 있던 값과 갱신할 값 중 작은 값으로 저장한다. // Math.min(이전 도착 지점 값, 갱신할 값);

 

 

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BACKJOON_001446.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split(/\r?\n/);

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

input.forEach((row) => {
  const [s, e, t] = row.split(" ").map(Number);
  if(s > D || e > D) return;
  if(map[s] === undefined) map[s] = [[e, t]]; 
  else map[s].push([e, t]);
});

const dp = Array.from({length: D + 1}, (_, i) => i);

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

  if(map[i] === undefined) continue;
  map[i].forEach(([e, t]) => {
    dp[e] = Math.min(dp[e], dp[i] + t);
  });
}

console.log(dp[D]);

 

 

회고

현재 코드는 메모리 낭비가 있는 코드라고 생각된다.

지름길은 최대 12개 이므로 map에 필요한 index는 최대 12개지만, 현재 코드는 시작 지점을 기준으로 저장하므로 중간에 사용하지 않는 index에는 undefined로 채워지게 된다....

문제의 정답을 통과하는데는 문제가 없다고 생각하여 일단 이렇게 만들었지만...

차라리 배열이 아닌 Map 자료 구조로 만드는게 좋을 것 같다!