백준 1285 - 동전 뒤집기

www.acmicpc.net/problem/1285

 

$N \times N$으로 놓여진 동전을 한행씩, 한열씩 뒤집을 수 있을 때 T의 갯수를 최소화 하는 문제이다.

 

이 문제는 $2^N$ 완전탐색을 통한 전처리 후 나머지를 그리디하게 결정하는 방법으로 풀 수 있다.

 

각 행을 뒤집는 경우를 완전탐색으로 결정한다고 해보자.

 

각 행에 대해 뒤집을지 말지 결정하는 경우의 수를 $2^N$의 시간 복잡도로 찾을 수 있다.

 

각 행에 대해 뒤집는 연산이 끝나면 각 열에 대해 뒤집었을 때와 뒤집지 않을 때의 T의 개수를 비교하여 T가 더 적은 쪽을 선택해나가는 방식으로 답을 구할 수 있다.

 

행이 아니라 열을 뒤집는 경우에 수에 대해 탐색하고 각 행을 뒤집을지 결정해도 상관없다.

 

총 시간복잡도는 $O(2^NN^2)$ 가 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

char field[20][20];
char mp[255];

int cnt = 1e9;

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

    int n;
    (cin >> n).get();
    
    mp['H'] = 'T', mp['T'] = 'H';

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            field[i][j] = cin.get();
        cin.get();
    }
    
    int bit = (1 << n) - 1;

    while (bit)
    {
        char newfield[20][20];
        copy(&field[0][0], &field[0][0] + 20 * 20, &newfield[0][0]);

        int cmpcnt = 0;

        for (int i = 0; i < n; ++i)
        {
            if (bit & (1 << i))
            {
                for (int j = 0; j < n; ++j)
                    newfield[i][j] = mp[newfield[i][j]];
            }
        }
        
        for (int k = 0; k < n; ++k)
        {
            int front = 0, back = 0;
            for (int s = 0; s < n; ++s)
            {
                if (newfield[s][k] == 'T')
                    ++front;
                else
                    ++back;
            }

            if (front > back)
                cmpcnt += back;
            else
                cmpcnt += front;
        }

        cnt = min(cnt, cmpcnt);
        --bit;
    }

    cout << cnt;
}