[JavaScript/DP] 백준 골드 5 : 2666 - 벽장문의 이동

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

2666번: 벽장문의 이동

---

📌 작성한 코드 

// 2666
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const [f, s] = input.shift().split(" ").map(Number);
const M = Number(input.shift());
const list = input.map(Number);

const dp = Array.from({ length: M + 1 }, () => Array.from({ length: N + 1 }, () => new Array(N + 1).fill(-1)));

const solve = (index, first, second) => {
    if (index >= M) return 0;
    if (dp[index][first][second] !== -1) {
        return dp[index][first][second];
    }

    const next = list[index];
    const firstMove = Math.abs(first - next) + solve(index + 1, next, second);
    const secondMove = Math.abs(second - next) + solve(index + 1, first, next);

    dp[index][first][second] = Math.min(firstMove, secondMove);

    return dp[index][first][second];
};

console.log(solve(0, f, s));

 

📌 설명 

재귀 + dp를 사용해서 최소 이동 횟수를 구해보았다. 

문제에서는 제시된 위치의 벽장문을 순서대로 열 것인데, 벽장문을 최소로만 이동해서 해당 문들을 열려고 한다.

 

간단하게 생각하면 그리디를 사용해서 열려 있는 곳 중 현재 벽장문에서 가장 가까운 곳을 찾아서 이동 시키면 될 것 같지만, 현재 위치에서 열려있는 양쪽문의 거리가 똑같다면 우리는 둘 중 어떤 문을 선택할지 고민하게 된다. 그렇다면 우리는 두가지 경우의 수를 모두 고려해야 하기 때문에 그리디로 문제를 해결 할 수 없다.

 

그렇다면 우리는 매 단계를 기억하고, 해당 단계 중 최솟값을 사용할 수 있는 dp를 떠올릴 수 있다.

 

이 때 매 단계마다 변경되고, 고려해야 하는 부분은 3가지가 존재한다.

(1) 현재 열려고 하는 문의 순서 번호 (벽장문 번호 아님 인덱스 번호)

(2) 첫번째로 열려있는 문의 위치

(3) 두번째로 열려있는 문의 위치 

 

dp[i][j][k] = j,k 벽장의 문이 열려있을 때 i 번째 인덱스의 문을 열기 위해 이동시켜야 하는 문의 최소 이동 횟수

- 첫번째 문과 두번째 문을 이동시켰을 때의 결과 중 최솟값을 dp에 저장한다.

 

solve(i,j,k) = j,k 벽장의 문이 열려있을 때 i 번째 인덱스에서 마지막 벽장 문 인덱스까지 이동했을 때 최소 이동 횟수 찾는 함수 

 

 

✅ 성공