[백준] 1149

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보다 작거나 같은 자연수이다.

출력

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

풀이

const rgb = () => {
  const [n, ...arr] = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((v) => v.split(" ").map(Number));
  let dp = Array.from({ length: n }, (v) => [0, 0, 0]);
  dp[0] = arr[0];
  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
    dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];
  }
  console.log(Math.min(...dp[n - 1]));
};

rgb();

반성회

테이블 정의하기

D[N][0] = N번째 집을 빨간색 (R) 으로 칠할 때 지금까지 든 최소비용

D[N][1] = N번째 집을 초록색 (G) 으로 칠할 때 지금까지 든 최소비용

D[N][2] = N번째 집을 파란색 (B) 으로 칠할 때 지금까지 든 최소비용

이때 N - 1번째 집은 N번째 집과 다른 색이어야 한다

점화식 찾기

D[N][0] 은 N번째 집이 빨간색이므로, N - 1번째 집은 무조건 녹색 혹은 파란색이 와야 한다

따라서 D[N][0]은 N - 1번째 집이 녹색일 때와 파란색일 때 중 금액의 최소인 것을 선택하고, N번째 집을 빨간 색으로 칠했을 때의 금액을 더하면 된다

D[N][1] 은 N번째 집이 초록색이므로, N - 1번째 집은 무조건 빨혹간혹 혹은색파란이 와야 한다

따라서 D[N][1]은 N - 1번째 집이 빨간색일 때와 파란색일 때 중 금액의 최소인 것을 선택하고, N번째 집을 초록색으로 칠했을 때의 금액을 더하면 된다

D[N][2] 는 N번째 집이 파란색이므로, N - 1번째 집은 무조건 빨간색 혹은 초록색이 와야 한다

따라서 D[N][2]는 N - 1번째 집이 빨간색일 때와 초록색일 때 중 금액의 최소인 것을 선택하고, N번째 집을 파란 색으로 칠했을 때의 금액을 더하면 된다

⇒ 점화식은

• D[N][0] = Math.min(D[N - 1][1], D[N - 1][2]) + arr[i][0];
• D[N][1] = Math.min(D[N - 1][0], D[N - 1][2]) + arr[i][1];
• D[N][2] = Math.min(D[N - 1][0], D[N - 1][1]) + arr[i][2];

초기값 정하기

위 점화식으로 풀 수 있는 N의 최소값이 1이므로, (N번째 값을 구하려면 N - 1번째 값이 필요함) 적어도 D[0] 의 모든 값을 알아야 풀 수 있다

D[0]은 앞에 아무 집도 색칠하지 않은 상태이므로, arr[0] 의 값 3개가 그대로 들어간다

풀기

위의 점화식을 그대로 for문 내에 넣은 후, D[n - 1] (N번째) 까지 구했다면 N번째 집을 색칠할 때까지 든 최소비용을 구한 것이므로 D[n - 1][0], D[n - 1][1], D[n - 1][2] 중 작은 값을 출력한다