[JavaScript] 백준 1149 : RGB거리

class : 4

level : silver 1

문제 링크 : RGB거리

1149번: RGB거리

My Solution

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
input = input.split('\n');
const N = Number(input.shift());
input = input.map(str=>str.split(' ').map(Number))
let DP = [];
input.forEach((value,index)=>{
    if(index===0)
        DP.push([value[0],value[1],value[2]]);
    else{
        DP.push([value[0]+Math.min(DP[index-1][1],DP[index-1][2]),value[1]+Math.min(DP[index-1][0],DP[index-1][2]),value[2]+Math.min(DP[index-1][0],DP[index-1][1])]);
    }
})
console.log(Math.min(DP[N-1][0],DP[N-1][1],DP[N-1][2]));

 

풀이방법

이 문제는 Dynamic Programming을 이용하여 쉽게 풀 수 있다.

DP라는 Array에 [i번째에 R을 칠할 수 있는 최솟값, i번째에 G를 칠할 수 있는 최솟값, i번째에 B를 칠할 수 있는 최솟값]의 형태로 집어 넣는다.

i번째에 R을 칠할 수 있는 최솟값을 구할때는 자신의 색을 제외한 i-1번째 값들 중 작은 것과 자신의 값을 더하여 i번째 집까지 칠하는 값을 구한다.

그 후 마지막에 3가지 색 중 가장 작은 값을 출력한다.

 

느낀점
Dynamic Programming을 이용하면 매우 빠르게 문제를 풀 수 있다.