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

[ 문제 ]

 

1285번: 동전 뒤집기 (acmicpc.net)

 

[ 접근방법 ]

 

같은 행 또는 열을 2번 뒤집으면 순서와 상관없이 원래대로 돌아간다.

즉, 각 행 또는 열을 뒤집을 것인지 말 것인지를 고려해주면 된다(몇 번 뒤집을 것인지는 중요하지 않다).

 

행과 열을 전부 뒤집을 필요도 없다.

n개의 행을 뒤집고 나서, 각각의 열을 보면서 가장 적게 나온 T 또는 H를 체크해주면 된다.

 

또한 뒤집는 행을 결정할 때 비트마스크를 활용했다.

 

n이 최대 20이므로 시간도 충분하다.

 

[ 소스코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, dt[22][22], arr[22];
int res = 400, cnt, sum;
string str;

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

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> str;
        for (int j = 0; j < n; j++)
        {
            dt[i][j] = str[j] == 'T' ? 1 : 0;
        }
    }

    for (int i = 0; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            arr[j] = i & (1 << j) ? 1 : 0;
        }

        sum = 0;
        for (int j = 0; j < n; j++)
        {
            cnt = 0;
            for (int k = 0; k < n; k++)
            {
                cnt += arr[k] ? 1 - dt[k][j] : dt[k][j];
            }
            sum += min(cnt, n - cnt);
        }
        res = min(res, sum);
    }

    cout << res;

    return 0;
}