[백준 2449] 전구 (C#, C++) - soo:bak

문제 링크

2449번 - 전구

설명

N개의 전구가 일렬로 놓여 있고, 연결된 같은 색 구간을 한 번에 다른 색으로 바꿀 수 있습니다.

모든 전구를 하나의 색으로 만드는 데 필요한 최소 색 변경 횟수를 구하는 문제입니다.

접근법

먼저, 구간 DP를 사용합니다. 각 구간을 한 색으로 만드는 최소 비용을 저장하고, 큰 구간은 작은 구간들을 병합하여 계산합니다.

다음으로, 구간을 두 부분으로 나눠서 각각 한 색으로 만든 후 병합합니다. 이때 왼쪽 구간의 대표 색과 오른쪽 구간의 대표 색이 다르면 병합 시 1회 추가 비용이 발생합니다. 대표 색은 각 구간의 왼쪽 끝 색으로 설정합니다.

이후, 모든 분할점에 대해 병합 비용을 계산하고 최솟값을 선택합니다. 길이 1인 구간은 이미 한 색이므로 비용이 0입니다.

Code

C#

using System;

namespace Solution {
  class Program {
    const int INF = 10_000_000;

    static void Main(string[] args) {
      var first = Console.ReadLine()!.Split();
      var N = int.Parse(first[0]);
      var K = int.Parse(first[1]);

      var c = new int[N];
      var arr = Console.ReadLine()!.Split();
      for (var i = 0; i < N; i++)
        c[i] = int.Parse(arr[i]);

      var dp = new int[N, N];
      for (var i = 0; i < N; i++)
        for (var j = 0; j < N; j++)
          dp[i, j] = INF;
      for (var i = 0; i < N; i++)
        dp[i, i] = 0;

      for (var len = 2; len <= N; len++) {
        for (var l = 0; l + len - 1 < N; l++) {
          var r = l + len - 1;
          for (var m = l; m < r; m++) {
            var cost = dp[l, m] + dp[m + 1, r];
            if (c[l] != c[m + 1])
              cost += 1;
            if (cost < dp[l, r])
              dp[l, r] = cost;
          }
        }
      }

      Console.WriteLine(dp[0, N - 1]);
    }
  }
}

C++

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

typedef vector<int> vi;

const int INF = 1e9;

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

  int N, K; cin >> N >> K;
  vi c(N);
  for (int i = 0; i < N; i++)
    cin >> c[i];

  static int dp[201][201];
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      dp[i][j] = INF;
  for (int i = 0; i < N; i++)
    dp[i][i] = 0;

  for (int len = 2; len <= N; len++) {
    for (int l = 0; l + len - 1 < N; l++) {
      int r = l + len - 1;
      for (int m = l; m < r; m++) {
        int cost = dp[l][m] + dp[m + 1][r];
        if (c[l] != c[m + 1])
          cost++;
        dp[l][r] = min(dp[l][r], cost);
      }
    }
  }

  cout << dp[0][N - 1] << "\n";

  return 0;
}