[백준 2482] 색상환 (C#, C++) - soo:bak

문제 링크

2482번 - 색상환

설명

N개의 색이 원형으로 배열된 색상환에서, 서로 인접하지 않게 K개를 선택하는 경우의 수를 구하는 문제입니다. 답은 1000000003으로 나눈 나머지를 출력합니다.

접근법

원형 배열에서는 첫 번째와 마지막이 인접하므로, 첫 번째 색을 고르는 경우와 고르지 않는 경우로 나누어 생각합니다.

첫 번째 색을 고르지 않는 경우, 나머지 N - 1개의 색을 일렬로 놓고 K개를 비인접하게 선택하는 문제가 됩니다. 첫 번째 색을 고르는 경우, 두 번째와 마지막 색은 선택할 수 없으므로 나머지 N - 3개에서 K - 1개를 비인접하게 선택하는 문제가 됩니다.

일렬로 놓인 n개에서 비인접하게 k개를 고르는 경우의 수는 동적 계획법으로 구합니다. 각 색에 대해 고르거나 고르지 않는 두 가지 선택이 있습니다. 고르지 않으면 이전까지의 경우의 수를 그대로 사용하고, 고르면 바로 이전 색은 건너뛰어야 하므로 두 칸 이전까지의 경우의 수를 사용합니다.

두 경우의 경우의 수를 더한 값이 답이 됩니다.

---

Code

C#

using System;

class Program {
  const int MOD = 1000000003;

  static int Line(int n, int k) {
    if (k == 0) return 1;
    if (n <= 0 || k > n) return 0;
    var dp = new int[n + 1, k + 1];
    for (var i = 0; i <= n; i++) dp[i, 0] = 1;
    if (n >= 1 && k >= 1) dp[1, 1] = 1;
    for (var i = 2; i <= n; i++) {
      var lim = Math.Min(i, k);
      for (var j = 1; j <= lim; j++)
        dp[i, j] = (dp[i - 1, j] + dp[i - 2, j - 1]) % MOD;
    }
    return dp[n, k];
  }

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var k = int.Parse(Console.ReadLine()!);
    if (k == 1) { Console.WriteLine(n % MOD); return; }
    if (k > n / 2 + n % 2) { Console.WriteLine(0); return; }

    var case1 = Line(n - 1, k);
    var case2 = Line(n - 3, k - 1);
    var ans = (case1 + case2) % MOD;
    Console.WriteLine(ans);
  }
}

C++

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

typedef vector<int> vi;
typedef vector<vi> vvi;

const int MOD = 1000000003;

int lineWays(int n, int k) {
  if (k == 0) return 1;
  if (n <= 0 || k > n) return 0;
  vvi dp(n + 1, vi(k + 1, 0));
  for (int i = 0; i <= n; i++) dp[i][0] = 1;
  if (n >= 1 && k >= 1) dp[1][1] = 1;
  for (int i = 2; i <= n; i++) {
    int lim = min(i, k);
    for (int j = 1; j <= lim; j++)
      dp[i][j] = (dp[i - 1][j] + dp[i - 2][j - 1]) % MOD;
  }
  return dp[n][k];
}

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

  int n, k; cin >> n >> k;

  if (k == 1) { cout << (n % MOD) << "\n"; return 0; }
  if (k > (n + 1) / 2) { cout << 0 << "\n"; return 0; }

  int case1 = lineWays(n - 1, k);
  int case2 = lineWays(n - 3, k - 1);
  int ans = (case1 + case2) % MOD;
  cout << ans << "\n";

  return 0;
}