백준[JS] > 1446번 지름길

2025. 3. 5. 23:28·🔒Algorithm

문제링크

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]);

 

 

'🔒Algorithm' 카테고리의 다른 글

백준[JS] > 23971번 ZOAC 4  (0) 2025.03.06
백준[JS] > 14719번 빗물  (0) 2025.03.06
백준[JS] > 20125번 쿠키의 신체 측정  (0) 2025.03.05
백준[JS] > 9655번 돌게임  (0) 2025.03.05
백준[JS] > 11403번 경로 찾기  (0) 2025.03.03
'🔒Algorithm' 카테고리의 다른 글
  • 백준[JS] > 23971번 ZOAC 4
  • 백준[JS] > 14719번 빗물
  • 백준[JS] > 20125번 쿠키의 신체 측정
  • 백준[JS] > 9655번 돌게임
devWarrior
devWarrior
  • devWarrior
    devWarrior
    devWarrior
  • 전체
    오늘
    어제
    • 🧩Dev (263)
      • ⭐FE (34)
      • 🔒Algorithm (155)
      • ➕Etc. (11)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
    • 글쓰기
    • 관리
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    코테
    프로그래머스
    dp
    Easy
    DFS
    자바스크립트
    구현
    leetcode
    Algorithm
    그리디
    react
    nodejs
    js
    티스토리챌린지
    자스
    백준
    javascript
    골드5
    node.js
    오블완
    Lv2
    실버3
    BFS
    실버2
    프론트엔드
    알고리즘
    실버1
    FE
    실버4
    코딩테스트
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
devWarrior
백준[JS] > 1446번 지름길
상단으로

티스토리툴바