RGB거리

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

96

예제 입력 2

3
1 100 100
100 1 100
100 100 1

예제 출력 2

3

예제 입력 3

3
1 100 100
100 100 100
1 100 100

예제 출력 3

102

예제 입력 4

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4

208

예제 입력 5

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력 5

253

정답

// 입력 받기 위한 readline 모듈 불러오기
const readline = require('readline');

// 표준 입력, 출력을 위한 인터페이스 생성
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

// 입력을 받을 배열
let input = [];

// 한 줄씩 입력 받는 함수
function inputLine(line) {
  input.push(line);
}

// DP 테이블 초기화 함수
function initDP(n) {
  const dp = new Array(n);

  for (let i = 0; i < n; i++) {
    dp[i] = new Array(3).fill(0);
  }

  return dp;
}

// 주어진 비용 중에서 최솟값을 구하는 함수
function getMinCost(costs) {
  return Math.min(...costs);
}

// RGB 거리 문제 풀이 함수
function solveRGBDistance(n, costs) {
  const dp = initDP(n); // DP 테이블 초기화

  // 첫 번째 집의 비용은 그대로 DP 테이블에 저장
  dp[0][0] = costs[0][0];
  dp[0][1] = costs[0][1];
  dp[0][2] = costs[0][2];

  // 두 번째 집부터 마지막 집까지 반복하며 최솟값을 구함
  for (let i = 1; i < n; i++) {
    // 이전 집과 겹치지 않는 색의 비용 중 최솟값을 현재 집의 비용과 더해서 저장
    dp[i][0] = costs[i][0] + getMinCost([dp[i-1][1], dp[i-1][2]]);
    dp[i][1] = costs[i][1] + getMinCost([dp[i-1][0], dp[i-1][2]]);
    dp[i][2] = costs[i][2] + getMinCost([dp[i-1][0], dp[i-1][1]]);
  }

  // 마지막 집의 색을 칠하는데 드는 비용 중 최솟값을 반환
  return getMinCost(dp[n-1]);
}

// 입력을 받기 위한 준비
rl.on('line', inputLine);
rl.on('close', () => {
  const n = Number(input[0]); // 집의 수
  const costs = []; // 각 집을 칠하는데 드는 비용

  // 각 집을 칠하는데 드는 비용을 2차원 배열로 변환
  for (let i = 1; i <= n; i++) {
    costs.push(input[i].split(' ').map(Number));
  }

  const result = solveRGBDistance(n, costs); // RGB 거리 문제 풀이

  console.log(result); // 결과 출력
});