백준 1285 동전뒤집기 c++ // 비트마스킹 개선방법

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

1285번: 동전 뒤집기

1. 비트마스킹 개선방법

행탐색(2^20) * 열탐색(2^20) -> 2^40 -> 터진다.

해결 : 행만바꾼후, 열은 최적해가 정해져있다. -> 열을 노가다로 탐색X

ex) HTT 가 열인경우, 뒤집으면 THH가 된다. -> 뒤집는게 최적해다!

THH가 열인경우, 안뒤집는게 최적해다!

결론 : 행만뒤집은후, t가 절반보다많으면 뒤집으면된다!

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

char a[24][24],origin[24][24];
int n,ret=987645321;

void copy() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            a[i][j] = origin[i][j];
        }
    }
}
void swap_hang(int r) {
    for (int i = 0; i < n; ++i) {
        if(a[r][i]=='T')
            a[r][i] = 'H';
        else if(a[r][i] == 'H')
            a[r][i] = 'T';
    }
}
void swap_yul(int r) {
    for (int i = 0; i < n; ++i) {
        if (a[i][r] == 'T')
            a[i][r] = 'H';
        else if (a[i][r] == 'H')
            a[i][r] = 'T';
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> origin[i][j];
        }
    }

    //행,열 모두뒤집 -> 2^40 -> 터짐
    //해결 : 행만뒤집 and 열은 최적해가 정해져있음!
    for (int subset1 = 0; subset1 < (1 << n); ++subset1) { //행
        //
        copy();
        for (int i = 0; i < n; ++i) {
            if (subset1 & (1 << i)) {
                swap_hang(i);
            }
        }

        int cnt = 0; //전체배열에서 t의갯수(최소화해야함)
        for (int i = 0; i < n; ++i) {
            int t = 0; //한행에서 T의갯수
            for (int j = 0; j < n; ++j) {
                if (a[j][i] == 'T') t++;
            }
            if (t > n/2) { //뒤집으면됨
                cnt += n - t;
            }
            else {
                cnt += t;
            }
        }
        ret = min(ret, cnt);
    }
    cout << ret;
    
    return 0;
}