백준[node.js] > 1149 RGB거리

문제링크

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

 

풀이

처음에는 가장 작은 수를 더하는 방식으로 하여 최솟값을 구하려고 생각했는데 아래와 같은 케이스를 생각해보니 그렇게 접근하면 안될 것 같다는 생각이 들었다. 

3

1 2 3

4 5 6

100 100 1

200 200 1

 

결국 모든 경우의 수를 탐색하기 위해선 아래와 같이 코드를 작성해야 한다.

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

let dp = Array.from({ length: input.length - 1 }, () => {
    return Array(3).fill(0);
});

let map = [];
for (let i = 1; i <= input.length - 1; ++i) {
    let arr = input[i].split(" ").map((n) => Number(n));
    map.push(arr);
}

for (let i = 0; i <= map.length - 1; ++i) {
    if (i === 0) {
        dp[0][0] = map[0][0];
        dp[0][1] = map[0][1];
        dp[0][2] = map[0][2];
    } else {
        dp[i][0] = map[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
        dp[i][1] = map[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
        dp[i][2] = map[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
    }
}

let min = Math.min(...dp.pop());
console.log(min);