[BOJ 17404] RGB거리 2

문제

RGB거리 2

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

 

 

풀이

설명

모든 집을 칠하는 비용의 최솟값을 구하는 문제입니다.

규칙은 다음과 같습니다.

• 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 합니다.
• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 합니다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 합니다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 합니다.

 

RGB거리 문제에서 규칙만 조금 바뀌었습니다. 첫 번째 집에서 고른 색은 마지막 집에서 고를 수 없습니다.

DP를 이용해 해결할 수 있습니다.

 

dp[i][j]는 i번째 집까지 색칠을 마쳤고, i번째 집을 j색으로 칠했을 때의 비용의 최솟값입니다.

 

i번째 집을 j색으로 칠했을 때의 최솟값은 (i - 1번째 집을 j가 아닌 색으로 칠했을 때의 최솟값) + (i번째 집을 j색으로 칠했을 때의 최솟값)입니다.

 

0번이 r, 1번이 g, 2번이 b라고 할 때, 점화식은 다음과 같습니다.

 

dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + r;

dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + g;

dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + b;

 

마지막 비용을 계산할 때, 첫 번째 집에서 고른 색을 제외한 색으로 칠해진 비용만을 가지고 계산하면 됩니다.

 

예시 코드

function solution() {
  const n = Number(input());
  const costs = Array.from({ length: n }, () => input().split(" ").map(Number));
  let answer = Infinity;

  for (let firstColor = 0; firstColor < 3; firstColor++) {
    const dp = Array.from({ length: n }, () => Array(3).fill(Infinity));
    dp[0][firstColor] = costs[0][firstColor];

    for (let i = 1; i < n; i++) {
      const [r, g, b] = costs[i];
      dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + r;
      dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + g;
      dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + b;
    }

    for (let lastColor = 0; lastColor < 3; lastColor++) {
      if (lastColor === firstColor) continue;
      answer = Math.min(answer, dp[n - 1][lastColor]);
    }
  }

  return answer;
}