boj-1149 RGB 거리(JavaScript)

문제

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

내 코드

const [N, ...arr] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const input = arr.map((houseCosts) => houseCosts.split(" ").map(Number));

function solution(n, rgb) {
  const DP = Array.from({ length: n + 1 }, () => 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][1], DP[i - 1][0]) + rgb[i - 1][2];
  }
  console.log(Math.min(...DP[n]));
}

solution(+N, input);

• 처음에는 1번째 집이 R,G,B를 선택하는 경우의 수를 구하고 이를 이 중 가장 작은 것을 가지고 다음 집을 구한다고 생각했다. 생각은 했는데 이를 코드로 어떻게 짜야할지 생각을 못해서 경우의수를 일일히 적어보고 패턴을 찾아보려고 했다.
• 하지만 못찾아서 다른 사람의 해설을 참고하였다. 문제가 복잡해보이지만 단순하게 생각하면 인접한 집끼리는 같은 색상을 가질 수 없다는 것이 전부이다.

우선, DP 배열을 만들고 해당 DP[i][0]은 i번째 집을 Red로 색칠하는 비용을 저장한다.

• DP[1] = input[0] 이 성립한다.
• 이후 i = 2 부터 반복문을 진행한다.
  1. DP[2]가 R로 색칠될 경우의 비용을 저장한다. ⇒ DP[2]가 R 이기 위해서는 DP[1]에서 G, B로 색칠되어야만 가능하다. 즉 DP[1]에서 G, B를 칠하는 비용 중 최소값을 구하고 이에 input의 2번째 집에 해당하는 비용 중 R을 색칠하는 비용을 더해주면 DP[2][0] 즉, 2번째 집을 R로 칠할 때 최소 비용을 구할 수 있다.
  2. DP[2][1]은 이전 집에서 R, B 중 최소값에다가 input의 2번째 집에 해당하는 비용 중 G을 색칠하는 비용을 더해주면 DP[2][1]의 최솟값을 구할 수 있다.