[백준 1149] RGB거리 (C#, C++) - soo:bak

문제 링크

1149번 - RGB거리

설명

N개의 집이 일렬로 배치되어 있고 각 집을 빨강, 초록, 파랑 중 하나의 색으로 칠해야 하며 인접한 집끼리 같은 색을 사용할 수 없는 상황에서 각 집을 각 색으로 칠하는 비용이 주어질 때, 모든 집을 칠하는 최소 비용을 구하는 문제입니다.

N은 2 이상 1,000 이하이고, 각 비용은 1,000 이하의 자연수입니다.

접근법

i번째 집의 최소 비용은 i-1번째 집의 색에만 의존하므로 동적 프로그래밍을 사용합니다.

dp[i][c]를 i번째 집을 색 c로 칠했을 때 0번째부터 i번째까지의 최소 비용으로 정의합니다. i번째 집을 빨강으로 칠하면 i-1번째 집은 초록 또는 파랑 중 비용이 작은 쪽이 됩니다. 초록과 파랑도 동일한 방식입니다.

예를 들어 비용이 [26, 40, 83], [49, 60, 57], [13, 89, 99]인 3개의 집이 있을 때:

• 첫 번째 집: dp[0] = [26, 40, 83]
• 두 번째 집을 빨강으로 칠할 때 첫 번째 집은 초록(40)과 파랑(83) 중 작은 40: dp[1][빨강] = 49 + 40 = 89
• 두 번째 집을 파랑으로 칠할 때 첫 번째 집은 빨강(26)과 초록(40) 중 작은 26: dp[1][파랑] = 57 + 26 = 83
• 세 번째 집을 빨강으로 칠할 때 두 번째 집은 초록과 파랑 중 작은 83: dp[2][빨강] = 13 + 83 = 96

각 집마다 세 가지 색을 계산하므로 시간 복잡도는 O(N)이고, 마지막 집의 세 색 중 최솟값이 답입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var dp = new int[n, 3];

      for (var i = 0; i < n; i++) {
        var line = Console.ReadLine()!.Split();
        dp[i, 0] = int.Parse(line[0]);
        dp[i, 1] = int.Parse(line[1]);
        dp[i, 2] = int.Parse(line[2]);
      }

      for (var i = 1; i < n; i++) {
        dp[i, 0] += Math.Min(dp[i - 1, 1], dp[i - 1, 2]);
        dp[i, 1] += Math.Min(dp[i - 1, 0], dp[i - 1, 2]);
        dp[i, 2] += Math.Min(dp[i - 1, 0], dp[i - 1, 1]);
      }

      var ans = Math.Min(dp[n - 1, 0], Math.Min(dp[n - 1, 1], dp[n - 1, 2]));

      Console.WriteLine(ans);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vector<array<int, 3>> dp(n);
  for (int i = 0; i < n; i++)
    cin >> dp[i][0] >> dp[i][1] >> dp[i][2];

  for (int i = 1; i < n; i++) {
    dp[i][0] += min(dp[i - 1][1], dp[i - 1][2]);
    dp[i][1] += min(dp[i - 1][0], dp[i - 1][2]);
    dp[i][2] += min(dp[i - 1][0], dp[i - 1][1]);
  }

  cout << min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << "\n";

  return 0;
}