[C++] 백준 1285번 동전 뒤집기

문제

N2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다.

N2개의 동전들의 초기 상태가 주어질 때, 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하는 동전 개수를 최소로 하려 한다. 이때의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다.

출력

첫째 줄에 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하여 놓일 수 있는 동전의 최소 개수를 출력한다.

풀이

먼저 열은 건드리지 않고 행만 뒤집는 모든 경우를 생각한다. 이는 2^n개의 가지수가 나올 것이다. 각 경우에 대해 1열부터 시작해 마지막 열까지 뒤집은 경우와 안 뒤집은 경우중 T가 더 적게 나오는 경우를 택한다.
마지막으로 비트마스킹을 이용해 check에 각 행의 뒤집기 여부를 기록하면 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n;
string str[20];
int dp[1048576];

int countT(){
  int ret = 0;
  for (int i=0; i<n; i++){
    int cnt = 0;
    for (int j=0; j<n; j++)
      if (str[j][i] == 'T')
        cnt++;
    // T가 더 많으면 뒤집은 결과 저장
    ret += min(cnt, n-cnt);
  }

  return ret;
}

void reverse(int line){
  for (int i=0; i<n; i++){
    if (str[line][i] == 'T') str[line][i] = 'H';
    else str[line][i] = 'T';
  }
}

int solve(int check){
  
  int &ret = dp[check];
  if (ret != -1) return ret;

  ret = countT();
  
  for (int next=0; next<n; next++){
    ret = min(ret, solve(check));
  }

  for (int next=0; next<n; next++){
    reverse(next);
    ret = min(ret, solve(check|(1<<next)));
    reverse(next);
  }

  return ret;
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);

  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  for (int i=0; i<n; i++){
    cin >> str[i];
  }

  memset(dp,-1,sizeof(dp));

  cout << solve(0);
}