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

<조건 분석>

 

1. N이 최대 20개. 20 X 20의 배열이 가능함.

2. 그러면 한 행, 한 열당 뒤집거나 안뒤집으니 2의 40승임.

3. 기존의 사고방식으로는 정면돌파 불가능함.

 

<문제 해결 포인트>

 

1. 행에서 한번 뒤집으면, 열은 이미 최소값이 정해져 있음.

2. 뒤집힌 행에서 열은 어차피 뒤집으면 되기 때문에, 앞이건 뒤건 상관없이 적은 갯수만 세면 된다는거임. 

3. 그렇게 되면 행이나 열만 뒤집으면 되니, 2의 20승으로 줄어듦.

4. 그리고 경우의 수 문제니 재귀를 돌면서 뒤집는 경우의 수 혹은 안뒤집는 경우의 수로 해보고, 최소값을 구하면 됨.

 

 

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> arr;
int res = 987654321;

void go(int here)
{
    if (here == N)
    {
        int temp = 0;
        for (int i = 0; i < N; i++)
        {
            int front = 0;
            int back = 0;
            for (int j = 0; j < N; j++)
            {
                if (arr[j] & (1 << i)) front++;
                else back++;
            }
            if (front > back) temp += back;
            else temp += front;
        }

        res = min(res, temp);
        return;
    }

    go(here + 1); // 안뒤집
    arr[here] = ~(arr[here]);
    go(here + 1); // 뒤집
}

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

    cin >> N;

    arr.resize(20);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            char temp;
            cin >> temp;

            if (temp == 'H')
            {
                arr[i] |= (1 << j);
            }
        }
    }

    go (0);

    cout << res;

    return 0;
}