[백준 1285] 동전 뒤집기 (C#, C++) - soo:bak

문제 링크

1285번 - 동전 뒤집기

설명

N×N 동전판에서 행 또는 열 단위로 동전을 뒤집어 뒷면이 보이는 동전의 개수를 최소화하는 문제입니다.

접근법

열을 뒤집을지 말지는 나중에 결정해도 됩니다. 어떤 열의 뒷면 개수가 절반을 넘으면 뒤집고, 아니면 그대로 두면 최적입니다. 따라서 행 뒤집기 상태만 모두 시도하면 됩니다.

N이 최대 20이므로 행 뒤집기 상태는 2의 20승 가지입니다. 각 열을 비트마스크로 저장해두면, 행 뒤집기 상태와 XOR 연산 후 비트 개수를 세는 것으로 뒷면 개수를 빠르게 구할 수 있습니다.

각 상태에서 모든 열의 뒷면 개수를 계산하고, 뒷면과 앞면 중 더 적은 쪽을 선택해 합산합니다. 이 값의 최솟값이 답입니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static int PopCount(int x) {
      var cnt = 0;
      while (x != 0) {
        cnt += x & 1;
        x >>= 1;
      }
      return cnt;
    }

    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var colMask = new int[n];
      for (var r = 0; r < n; r++) {
        var line = Console.ReadLine()!;
        for (var c = 0; c < n; c++) {
          if (line[c] == 'T')
            colMask[c] |= (1 << r);
        }
      }

      var limit = 1 << n;
      var best = int.MaxValue;

      for (var mask = 0; mask < limit; mask++) {
        var sum = 0;
        for (var c = 0; c < n; c++) {
          var tail = PopCount(colMask[c] ^ mask);
          sum += Math.Min(tail, n - tail);
          if (sum >= best)
            break;
        }
        if (sum < best)
          best = sum;
      }

      Console.WriteLine(best);
    }
  }
}

C++

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

typedef vector<int> vi;

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

  int n; cin >> n;
  vi colMask(n, 0);
  for (int r = 0; r < n; r++) {
    string line; cin >> line;
    for (int c = 0; c < n; c++) {
      if (line[c] == 'T')
        colMask[c] |= (1 << r);
    }
  }

  int limit = 1 << n;
  int best = INT_MAX;

  for (int mask = 0; mask < limit; mask++) {
    int sum = 0;
    for (int c = 0; c < n; c++) {
      int tail = __builtin_popcount(mask ^ colMask[c]);
      sum += min(tail, n - tail);
      if (sum >= best)
        break;
    }
    best = min(best, sum);
  }

  cout << best << "\n";

  return 0;
}