[비트마스킹 / BOJ 1285 / C++] 동전 뒤집기

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

1285번: 동전 뒤집기

1) 0과 1로 이루어진 이진수라고 생각한다.
2) 모든 행을 뒤집는 경우를 백트래킹으로 찾아본다.
3) 각각의 경우의 수마다 뒤집어야할 열들을 찾아본다.
4) T의 개수가 최소가 되는 순간을 찾는다.

진짜 생각하는게 어렵다.......... 근데 감만잡으면 확실히 이해할 수 있다.

 

일단 문제를 이해해보자!!

 

딱 보면은 열과 행으로 나누어서 0번째 열부터 N-1번째 열까지, 각각의 열을 뒤집었을때의 경우의 수와 행을 뒤집었을 때의 경우의 수와 나눠서 구해야할 것 같다!!

 

단순하게 생각해보면,

1) 한개의 열을 뒤집었을때 T의 개수를 본다.

2) 뒤집은 열을 원래대로 돌려둔다.

3) 다른 열을 선택해 뒤집고 1),2)과정을 반복한다.

4) 행 역시 마찬가지로 1),2),3)의 과정을 반복한다.

5) 각각의 경우의 수 중 T가 가장 적게 나온 경우들을 택한다!

6) 5)에서 나온 각각의 경우의 수에 대해 1)~5)과정을 반복한다.

7) T의 개수가 더이상 변하지 않으면 해당 T의 개수를 출력하고 종료한다.

 

딱 봐도 시간복잡도가 아득해질 것 같다. NXN 배열을 만들어서 for문을 몇번씩 돌려야한다.

 

그런데 주어진 문제를 보면 H, T 딱 2가지 경우만 확인하면 된다.

 

즉, 이를 다시 말하면 비트연산자를 응용하면 된다는 뜻이다.

 

그렇다면, 주어진 예시를 다음처럼 하나의 숫자로 표현할 수 있다.

보라색은 각 행에 해당하는 숫자들, 주황색은 각 열에 해당하는 숫자들이다.

 

하지만 문제가 있다. 이렇게 줄여도 뒤집는 경우의 수를 생각해보면, N<=20 이므로 

시간복잡도는 무려 2^40이다.

 

반절로 줄일 수 있는 방법이 있다. 일단 행만 봐보자. 모든 행을 뒤집는 경우들은 백트래킹을 이용하면 쉽게 구할 수 있다.

 

그리고나서 열을 뒤집어보자. 가만 생각해보면 열은 모든 경우의 수를 뒤질 필요가 전혀 없다!!

 

임의의 열을 선택할때, 그 열이 {HHH} 이면 뒤집을건가??? {HHT}는???

 

H가 많이 나오는 조합을 만들어야하므로 당연~~~히 뒤집어볼 필요도 없다.

{TTH}는 뒤집으면 {HHT}가 나오므로 뒤집을 가치가 있다.

 

그렇다. 모든 행의 경우의 수를 조사해보면 선택해야할 열들은 자동으로 정해져있다!!

 

이것을 이해했으면 이제 구현의 단계이다. 구현도 결코 만만치 않다. 끝까지 도전해보자!!

 

 

 

#include <bits/stdc++.h>

using namespace std;

int N, res=INT_MAX;
int bd[25]; // row

void go(int here){
    if(here == N+1){
        int sum = 0;
        for(int i = 1 ; i <= (1<<(N-1)) ; i*=2){
            
            int cnt = 0;
            for(int j = 0 ; j < N ; j++) if(bd[j]&i) cnt++; // T의 개수 세기.
            
            sum += min(cnt, N-cnt); // T의 개수가 H의 개수보다 많을 경우 뒤집어주기.
            
        }
        
        res = min(sum, res);
        
        return;
    } // 끝점에 도착. 각 col에서 T가 H보다 많은 것은 뒤집기!!
    
    
    go(here+1); // 안뒤집을 때
    bd[here] = ~bd[here];
    go(here+1); // 뒤집을 때
    bd[here] = ~bd[here]; // 원상 복구.
    
    return;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 0 ; i < N ; i++){
        string tmp="";
        cin >> tmp;
        
        int value = 1;
        for(int j = 0 ; j < N ; j++){
            if(tmp[j]=='T') bd[i] |= value; // j번째 비트 키기.
            value *= 2;
        }
    }
    
    go(0);
    
    cout << res;
    
    
    return 0;
}