[백준 알고리즘] Node.js 1149. RGB거리

1. 문제

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

1149번: RGB거리

 

2. 풀이

1) 이전에 사용했던 색상을 사용할 수 없다.

2) 이전 색상을 제외한 값을 더하면서 진행한다 - DP 이용!

3) 색상은 빨강, 초록, 파랑 3가지의 색상 중 하나를 사용한다.

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const n = +inputs.shift();
const dp = [];
for(let i = 0; i < n; i++){
    dp.push(inputs[i].split(' ').map(Number));
}

for(let i = 1; i < n; i++){
  for(let j = 0; j < 3; j++){
    let prev;

    if(j === 0) prev = Math.min(dp[i-1][j+1], dp[i-1][j+2])
    else if(j === 1) prev = Math.min(dp[i-1][j-1], dp[i-1][j+1])
    else prev = Math.min(dp[i-1][j-2], dp[i-1][j-1])

    dp[i][j] += prev;
  }
}

console.log(Math.min(...dp[n-1]));

- j는 색상의 값으로 최대 3까지이다. dp를 이용하기 때문에 1부터 시작.

- i는 집의 개수이다. 최대 n까지.

 

3. 정리 

- 처음에 코드를 작성할 때 이전 색상을 사용해서는 안된다는 조건을 사용하지 않아 답을 구할 수 없었다.

- dp에 대한 개념을 어느정도 이해할 수 있었다.

 

4. DP에 대해 내가 이해한 내용.

- 이미 했던 연산이 반복되는 결점을 보완하기 위해 사용.
- 재귀에서 반복되던 연산을 없앤 알고리즘.
- 한번 계산된 결과를 저장해두었다가 활용하는 방식으로 중복 계산을 줄이는 것을 메모이제이션이라 함.
- TOP-DOWN 이나 BOTTOM-UP 방식을 사용.
-> TOP-DOWN은 큰수부터 작은 수 순서로, BOTTOM-UP은 반대.

** 기존 값에 연산한 값을 추가로 연산하여 저장한다!!