[BOJ 1149] RGB거리

문제

RGB거리

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

 

 

풀이

설명

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

 

규칙은 다음과 같습니다.

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

 

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));
  const dp = Array.from({ length: N + 1 }, () => Array(3).fill(Infinity));
  dp[0] = [0, 0, 0];

  for (let i = 1; i <= N; i++) {
    const [r, g, b] = costs[i - 1];
    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;
  }

  return Math.min(...dp[N]);
}