[1285] 동전 뒤집기

https://www.acmicpc.net/problem/1285

1285번: 동전 뒤집기

<문제>

행에대해 브루트포스, 열에대해 그리디를 적용한다.

브루트포스는 (1<<n)-1번 반복하고, 그리디는 해당 열에 포함된 'H'와 'T'의 개수중 작은걸 고른다.

1열부터 순차적으로 탐색한다면, 각각의 열에대해 뒤집는 연산을 했는지는 완전히 독립적이므로

단순히 해당열중 작은걸 고른다는 접근이 정당하다.

1<<20이 거의 100만이므로, 행과 열 모두에 브루트포스를 적용할수는 없다. (100만*100만 > 6e8)

연산횟수는 2^N*N^2정도이므로 최종적으로 O(2^N)

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, a[22][22], clone[22][22];
void toggleY(int sy) {
    for (int i = 0; i < n; i++) a[sy][i] = 1 - a[sy][i];
}
int countAnswer(void) {
    int ret = 0;
    for (int i = 0; i < n; i++) {
        int temp = 0;
        for (int j = 0; j < n; j++) temp += a[j][i];
        ret += (min(temp, n - temp));
    }
    return ret;
}
int main(void) {
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (j = 0; j < n; j++) {
            if (s[j] == 'T') a[i][j] = 1;
            clone[i][j] = a[i][j];
        }
    }
    const int BIT = (1 << n) - 1;
    int ans = 54321;
    for (int bty = 0; bty <= BIT; bty++) {
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++) a[i][j] = clone[i][j];
        for (i = 0; i < n; i++)
            if (bty & (1 << i)) toggleY(i);
        int ret = countAnswer();
        ans = min(ret, ans);
    }
    cout << ans;
    return 0;
}