[백준 1014] 컨닝 (C#, C++) - soo:bak

문제 링크

1014번 - 컨닝

설명

교실에 학생들을 앉히되, 컨닝을 방지하기 위해 좌우 및 대각선 앞쪽에 다른 학생이 없도록 배치할 때 최대 몇 명을 앉힐 수 있는지 구하는 문제입니다. 일부 자리는 부서져서 앉을 수 없습니다.

접근법

가로 길이가 최대 10이므로 한 행의 배치 상태를 비트마스크로 표현할 수 있습니다. 각 비트가 해당 자리에 학생이 앉았는지를 나타냅니다.

먼저 한 행 내에서 유효한 배치를 모두 찾습니다. 같은 행에서 바로 옆자리에 학생이 있으면 컨닝이 가능하므로, 연속된 두 비트가 모두 1인 배치는 제외합니다. 또한 부서진 자리에는 앉을 수 없으므로 해당 위치의 비트가 1이면 안 됩니다.

다음으로 행 간의 관계를 확인합니다. 현재 행의 학생이 바로 앞 행의 좌상단이나 우상단에 있는 학생을 볼 수 있으면 컨닝이 가능합니다. 따라서 현재 행의 배치와 이전 행의 배치를 비교하여, 대각선 위치에 동시에 학생이 있는 경우를 제외해야 합니다.

이를 바탕으로 동적 프로그래밍을 수행합니다. 각 행마다 가능한 모든 유효 배치에 대해, 이전 행의 배치와 충돌이 없는 경우만 전이합니다. 각 상태에서 앉은 학생 수를 누적하면서 최댓값을 갱신합니다.

마지막 행까지 계산한 후 모든 가능한 배치 중 최댓값이 정답입니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static int CountBits(int x) {
    var c = 0;
    while (x > 0) { c += x & 1; x >>= 1; }
    return c;
  }

  static void Main() {
    var t = int.Parse(Console.ReadLine()!);
    while (t-- > 0) {
      var nm = Console.ReadLine()!.Split();
      var n = int.Parse(nm[0]);
      var m = int.Parse(nm[1]);

      var ban = new int[n];
      for (var i = 0; i < n; i++) {
        var line = Console.ReadLine()!;
        var mask = 0;
        for (var j = 0; j < m; j++) if (line[j] == 'x') mask |= (1 << j);
        ban[i] = mask;
      }

      var valid = new List<int>();
      var maxMask = 1 << m;
      for (var k = 0; k < maxMask; k++)
        if ((k & (k << 1)) == 0) valid.Add(k);

      var dp = new int[n, maxMask];
      for (var i = 0; i < n; i++)
        for (var k = 0; k < maxMask; k++)
          dp[i, k] = -1;

      foreach (var k in valid)
        if ((k & ban[0]) == 0) dp[0, k] = CountBits(k);

      for (var i = 1; i < n; i++) {
        foreach (var k in valid) {
          if ((k & ban[i]) != 0) continue;
          foreach (var pk in valid) {
            if (dp[i - 1, pk] < 0) continue;
            if ((k & (pk << 1)) != 0 || (k & (pk >> 1)) != 0) continue;
            var cand = dp[i - 1, pk] + CountBits(k);
            if (cand > dp[i, k]) dp[i, k] = cand;
          }
        }
      }

      var ans = 0;
      for (var k = 0; k < maxMask; k++) if (dp[n - 1, k] > ans) ans = dp[n - 1, k];
      Console.WriteLine(ans);
    }
  }
}

C++

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

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

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

  int t; cin >> t;
  while (t--) {
    int n, m; cin >> n >> m;
    vi ban(n, 0);
    for (int i = 0; i < n; i++) {
      string s; cin >> s;
      for (int j = 0; j < m; j++) if (s[j] == 'x') ban[i] |= (1 << j);
    }

    vi valid;
    int maxMask = 1 << m;
    for (int k = 0; k < maxMask; k++)
      if ((k & (k << 1)) == 0) valid.push_back(k);

    vvi dp(n, vi(maxMask, -1));
    auto bits = [](int x) { return __builtin_popcount(x); };

    for (int k : valid)
      if ((k & ban[0]) == 0) dp[0][k] = bits(k);

    for (int i = 1; i < n; i++) {
      for (int k : valid) {
        if (k & ban[i]) continue;
        for (int pk : valid) {
          if (dp[i - 1][pk] < 0) continue;
          if ((k & (pk << 1)) || (k & (pk >> 1))) continue;
          dp[i][k] = max(dp[i][k], dp[i - 1][pk] + bits(k));
        }
      }
    }

    int ans = 0;
    for (int k = 0; k < maxMask; k++) ans = max(ans, dp[n - 1][k]);
    cout << ans << "\n";
  }

  return 0;
}