동전 뒤집기
풀이
비트 마스킹 문제인데 아직 어색하다.
우선 아이디어 1. 같은 자리를 두 번 이상 뒤집는 것은 아무런 의미가 없다.
그렇기에 모든 가로에 대해 뒤집는 경우 2^20을 해보고, 세로에 대해 그리디하게 뒤집으면 된다.
그러면 시간 복잡도는 2^n * n^2이니까 충분히 해결이 가능하다.
계속 시간 초과가 나서 다른 사람들은 어떻게 했나 봤는데 백트래킹으로 한 사람이 없다.
그래도 30분 정도 해매다보니 최적화 시킬 수 있는 부분을 찾어서 고쳤더니 맞았다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c;
int n, m, t;
cin >> n;
string s;
vector<int> coin(n,0);
for(int i=0;i<n;i++){
cin >> s;
for(int j=0;j<n;j++){
if(s[j]=='H')coin[i] = coin[i]*2 + 1;//앞면은 1
else coin[i] = coin[i]*2; //뒷면은 0
}
}
int mi = 1e9;
vector<int> check(n, 0);
function <void(int, int)> back = [&](int k, int x){
if(k==n/2+1)return;
int total=0;
for(int i=0;i<n;i++){
int cnt=0;
for(int j=0;j<n;j++){
if((coin[j]>>i)&1) cnt++; //i번째가 1이면
}
total += min(cnt, n-cnt);
}
mi = min(total, mi);
for(int i=x;i<n;i++){
if(check[i]==0)
coin[i] ^= (1<<n)-1;
check[i]=1;
back(k+1, i+1);
check[i]=0;
coin[i] ^= (1<<n)-1;
}
};
back(0, 0);
cout << mi;
return 0;
}