[백준 1149] RGB거리 with Node.js

문제 링크

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

1149번: RGB거리

풀이

const solve = (n, rgb) => {
  dp = [...new Array(n+1)].map(v => new Array(3).fill(0));
  dp[1] = rgb[0];
  for (let i=2; i<=n; i++) {
    dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + rgb[i-1][0];
    dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + rgb[i-1][1];
    dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + rgb[i-1][2];
  }
  console.log(Math.min(...dp[n]));
};

const [n, ...rgb] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
solve(+n, rgb.map(cost => cost.split(' ').map(v => +v)));

dp[n][0]을 n번째 집을 빨간색으로 칠했을 때 전체 비용의 최솟값,

dp[n][1]을 n번째 집을 초록색으로 칠했을 때 전체 비용의 최솟값,

dp[n][2]를 n번째 집을 파란색으로 칠했을 때 전체 비용의 최솟값이라 하겠다.

 

dp[n][0](n번째 집이 빨간색일 때 최소비용)을 구하려면

dp[n-1][1](n-1번째 집이 초록색일 때 최소비용)과 dp[n-1][2](n-1번째 집이 파란색일 때 최소비용)

둘 중 더 작은 값에 rgb[n][0](n번째 집을 빨간색으로 칠하는 비용)를 더하면 된다.

 

따라서 아래와 같은 점화식을 세울 수 있다.

dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + rgb[n][0]

dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + rgb[n][1]

dp[n][2] = min(dp[n-1][0], dp[n-1][1]) + rgb[n][2]

 

(위 코드에서는 dp와 rgb의 인덱스가 1씩 차이가 나기 때문에 rgb의 인덱스에서 1을 빼주었다)