[알고리즘] 백준 1285 동전뒤집기 // 비트마스킹, 상태가 2개면 비트마스킹을 생각

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

* 행동영역

상태가 2개면 비트마스킹을 생각하라

* 풀이

• 일단 시간복잡도가 2^40 아닌가? -> 각행, 각열을 완탐
• but, 행만 완탐후, 열은 최적해가 정해져있음 -> 직접뒤집을필요x, 상태가 2개이므로 절반보다 크면 뒤집고 아니면 안뒤집으면 됨 -> 2^20
• 핵심은 동전의 상태가 2개-> 0과 1 비트 숫자 1개로 상태를 저장하는 것임
  • 배열에 넣는경우, 뒤집는 연산 for(~~~) 을 직접해야함.
• a[i] : 행 i 의 상태 저장

• 재귀함수
  • go(here) : here번째 행의 동전을 뒤집은경우, 안뒤집은경우
  • 동전을 뒤집는 연산을 ~ 으로 구현
  • 백트래킹으로 완전탐색

• 리턴조건
  • n이 다찼을때,
  • 각 열 (|) 을 탐색 할 변수 i : 1, 2, 4, 8 ... // i++ 아님에주의
  • a[j]와 i 를 & 연산하면 각 열(|)이 켜져있는지 알수있음

• 이때, T의 갯수를 t라고하면 H의 갯수는자동으로 n-t임
• T의 갯수가 n/2보다 크면, 뒤집는게 최적임 -> sum+= n-t
• 아니면, 안뒤집는게 최적 -> sum+=t

 

* 전체코드

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

int n,ret=987654321;
int a[44]; //a[i] : i 행 의 상태를 숫자 1개로 나타냄

void go(int here) {
    if(here==n+1) {
        /**
         *  i: 1 2 4 를 돌면서 | T의 갯수검사, 열 검사 위한 변수
         *  j: a[1] a[2] a[3] 행의 상태 탐색위한 변수
         **/
        int sum=0; // 현재 상태에서 최적의 t의갯수
        for(int i=1; i<= (1<<(n-1)); i*=2) { // ++i 아님에 주의!!, (n-1)에 괄호쳐야함에 주의!
            int t=0; //t의 갯수
            for(int j=1; j<=n;++j) {
                if(a[j] & i) {
                    t++;
                }
            }
            if(t > n/2) { //뒤집는게 최적 , t>n 아님에 주의!
                sum+=n-t;
            }
            else {
                sum+=t; //안뒤집는게 최적
            }
        }
        ret=min(ret,sum);
        return;
    }

    a[here]= ~a[here]; // 뒤집는경우
    go(here+1);
    a[here]= ~a[here]; // 안뒤집는경우
    go(here+1);
}

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

    /**
     *  124
     *  HHT -> 4 로 만들기
     */
    for(int i=1;i<=n;++i) {
        string s;
        cin>>s;
        int val=1;
        for(int j=0;j<n;++j) {
            if(s[j]=='T') a[i] |=val;
            val*=2;
        }
    }

    go(1);

    // for(int i=1;i<=n;++i) {
    //     cout<<a[i]<<" ";
    // }

    cout<<ret;
    
    return 0;
}