[백준/BOJ] 1285 동전 뒤집기 - 접근과 풀이 (c++)

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

1285번: 동전 뒤집기

비슷한 문제를 푼 기억때문에 날로 먹은 문제

---

접근 방법

 

20*20 배열을 뒤집으며 최솟값을 찾는 문제. 

 

완전탐색으로 할 경우 40개의 상태를 가지므로 2^40 = 1조이고, 이는 죽었다 깨어나도 정해가 아니다.

 

비겁하지만 알고리즘 분류를 보니 비트마스킹이 포함되어 있었다. 

나는 비트마스킹 문제중에 불 끄기 문제를 며칠동안 붙잡다가 풀이를 보았을때의 생생한 충격이 아직 남아있었다.

구현이나 복잡한 알고리즘이 존재하지 않는데 도저히 떠올릴 수 없는 아이디어가 플레티넘의 난이도의 실체였다.

 

그래서 해당 문제와 비슷한 방식으로 접근하니 매우 쉽게 아이디어가 떠올랐다.

이 문제도 아이디어만 안다면 매우 쉽게 풀린다.

 

 

N*N개의 상태를 전부 조사할 수는 없고, 세로로 N개의 행의 뒤집은 상태만을 완전탐색으로 나타낸다. 

이때 크기 N의 bool 배열을 사용해도 좋으나 N은 최대 20이므로  int형 변수 하나에 저장하는 비트마스킹 방식을 사용하자.

 

세로로 N개의 행을 전부 뒤집었다면, 가로로 N개의 열을 뒤집어 줘야한다. 

이때 가로 N개의 상태를 전부 탐색 할 필요가 없고, 각 열을 뒤집는 것은 다른 열의 상태에 영향을 미치지 않으므로 뒷면의 개수가 최소가 되게 그리디한 방법만을 선택한다.

 

위의 방법을 사용하면 O(2^N * N^2) 시간에 풀 수 있다.

---

풀이

 

tag : bitmasking, greedy

 

#include<iostream>
#include<cstring>
using namespace std;
int N,ans=987654321;
char arr[21][21];
void solve(int bit){
  /** 1~N행의 뒤집은 상태를 나타내는 bit*/
  char cpy[21][21];
  memcpy(cpy, arr, sizeof(arr));

  for (int i = 0; i < N;i++){
    if(bit & (1<<i)){ //i번째비트가 1이면 i행 뒤집음
      for (int j = 0; j < N;j++)
        cpy[i][j]= (cpy[i][j] == 'H') ? 'T' : 'H';
    }
  }

  int sum = 0;
  for(int j = 0; j < N;j++){
    int cntT = 0;
    for (int i = 0; i < N;i++)
      cntT += (cpy[i][j] == 'T'); //T 개수 세기

    sum += min(cntT, N - cntT);
  }
  ans = min(ans, sum);

}
int main(){
  cin >> N;
  for (int i = 0; i < N;i++){
    for (int j = 0; j < N;j++)
      cin >> arr[i][j];
  }
  for (int i = 0; i < (1 << N); i++)
    solve(i);
  cout<<ans;
}