[백준 c++] 1285 동전 뒤집기

문제 설명

https://www.acmicpc.net/problem/1285
N^2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다.
이들 N^2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 수행할 수 있다.

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

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

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

아이디어

제한시간이 6초나 주어지길래 모든 경우의 수를 다 계산해도 되는건가 했는데
시간복잡도를 대략 계산해보면 2^40으로 모든 경우의 수를 계산할 수 없었다.
따라서 브루트포스, 그리디 알고리즘을 이용해서 풀어야했다.

1. 비트마스킹으로 열을 기준으로 뒤집는 경우의 수를 구한다.
2. 그렇게 열을 뒤집었을 때 각 행을 뒤집을지 말지 최적해를 찾는다.

ex)
N=3일 때 열을 뒤집는 경우의 수 => 000,001,010,011,100,101,110,111

열을 뒤집고 나서 어떤 행에 동전 뒷면이 (2/N)개보다 많다면 뒤집는 게 최적해일 것이다.

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
char origin[21][21], m[21][21];
vector<int> res;
void reverse_c(int x) //열뒤집기 ||
{
    for (int i = 0; i < n; i++)
    {
        if (m[i][x] == 'T')
        {
            m[i][x] = 'H';
        }
        else if (m[i][x] == 'H')
            m[i][x] = 'T';
    }
}
void reverse_r(int y) //행뒤집기 --
{
    for (int i = 0; i < n; i++)
    {
        if (m[y][i] == 'T')
            m[y][i] = 'H';
        else if (m[y][i] == 'H')
            m[y][i] = 'T';
    }
}
void count()
{
    int t_cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (m[i][j] == 'T')
                t_cnt++;
        }
    }
    res.push_back(t_cnt);
}
void check()
{
    for (int i = 0; i < n; i++)
    {
        int cnt = 0;
        for (int j = 0; j < n; j++)
        {
            if (m[i][j] == 'T')
                cnt++;
        }
        if (cnt >= (n / 2))
            reverse_r(i);
    }
}
void m_copy()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            m[i][j] = origin[i][j];
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> origin[i][j];
        }
    }

    for (int i = 0; i < (1 << n); i++)
    {
        m_copy();
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                reverse_c(j);
            }
        }
        check();
        count();
    }
    sort(res.begin(), res.end());
    cout << res[0] << "\n";
}