백준 1285번 동전 뒤집기( C++ )

문제

https://www.acmicpc.net/problem/1285

 

해설

비트마스킹을 통해 모든 경우의 수를 확인

2의 40승의 경우의 수가 나와 시간초과가 발생 => 행 or 열 중에 하나만 확인으로 2의 20승을 만들고

적은 경우의 수를 택하는 방식 사용

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
const int INF = 987654321;
int ret = INF, n;
string line;
char mp[24][24];
char tmp[24][24];
 
void copy_arr(char arr[24][24], char arr2[24][24])
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      arr[i][j] = arr2[i][j];
    }
  }
}
 
void reversed(int num)
{
  for (int i = 0; i < n; i++)
  {
    if (mp[i][num] == 'T')
    {
      mp[i][num] = 'F';
    }
    else
    {
      mp[i][num] = 'T';
    }
  }
}
 
void go(int num)
{
  for (int i = 0; i < n; i++)
  {
    if (num & (1 << i))
    {
      reversed(i);
    }
  }
  int tmp = 0;
  for (int i = 0; i < n; i++)
  {
    int tmp2 = 0;
    for (int j = 0; j < n; j++)
    {
      if (mp[i][j] == 'T')
      {
        tmp2++;
      }
    }
    tmp += min(tmp2, n - tmp2);
  }
  ret = min(ret, tmp);
}
 
int main()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> line;
    for (int j = 0; j < n; j++)
    {
      mp[i][j] = line[j];
    }
  }
 
  copy_arr(tmp, mp);
 
  for (int i = 0; i < (1 << (n)); i++)
  {
    copy_arr(mp, tmp);
    go(i);
  }
 
  cout << ret;
}