[비트마스킹][브루트포스] 1285 동전 뒤집기 c++ 구현

목차

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

문제

 

문제 구현 방향 및 아이디어

아이디어가 필요한 문제였다. 생각보다 더 어려웠다....

 

 

참고

아래 풀이는 비트 마스킹의 이해가 필요하니 다음을 참고하자

https://be-senior-developer.tistory.com/134

[비트 마스킹][c++] 개념과 활용 방법에 대해서 알아보자

 

 

 

1. 가로와 세로에 대한 최적해

가로 세로를 모두 참색하게 되면 2^40의 시간 복잡도로 탐색할 수 없다. 따라서 다르게 생각해보아야 한다.

가로만 탐색하고 세로는 정해져 있는 것이 아닐까? 

 

H	H	T
T	H	H
T	H	T

 

첫번째 가로를 바꾼 뒤

T	T	H
T	H	H
T	H	T

 

첫째 세로 이외에 바꿀 이유가 없다.

H	T	H
H	H	H
H	H	T

 

가로열을 바꾼 뒤에 굳이 H가 적어지게끔 세로열을 바꿀 필요가 없기 때문에 2^20으로 시간복잡도가

비약적으로 줄게 된다.

 

2. 배열 비트로 나타내기

H	H	T
T	H	H
T	H	T

 

이 이차원 배열을 T 기준으로 비트로 표현하면 다음과 같다.

0	0	4
1	0	0
1	0	4

따라서 4 1 5가 나오게 된다.

 

변환 코드

int coins[21] = { 0 };
int main() {
	string str;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> str;
		int num = 0;
		for (int j = 0; j < N; j++) {
			if (str[j] == 'T') {
				num += pow(2, j);
			}
		}
		coins[i] = num;
	}
	for(auto p: coins)
    	cout << p << " ";
	

}

 

 

3. 배열 뒤집기는 ~, 토글은 ^, 검사는 &

void go(int here) {
	if (here == N - 1) {
		for (int i = 0; i < N; i++) {
			int cnt = 0;
			for (int j = 0; j < N; j++) {  //비트 켜져있는지 확인
				if (coins[j] & (1 << i))
					cnt++;  //켜져있으면 카운트
			}
			if (cnt > N - cnt) {   //T가 많을 경우 토글해주기
				for (int p = 0; p < N; p++) {  //모든 i번째 비트 토글
					coins[p] ^= (1 << i);
				}
			}
		}
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (coins[i] & (1 << j)) {  //T의 개수 세기(켜진 비트 세기)
					cnt++;
				}
			}
		}
		minTail = min(minTail, cnt);
		return;
	}

	go(here + 1);
	coins[here] = ~coins[here]; //뒤집어 주기
	go(here + 1);
}

 

코드 구현

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stack>
#include<math.h>
using namespace std;



int N;
int coins[21] = { 0 };
//T를 기준으로
int minTail = 9999;

void go(int here) {
	if (here == N - 1) {
		for (int i = 0; i < N; i++) {
			int cnt = 0;
			for (int j = 0; j < N; j++) {
				if (coins[j] & (1 << i))
					cnt++;
			}
			if (cnt > N - cnt) {
				for (int p = 0; p < N; p++) {
					coins[p] ^= (1 << i);
				}
			}
		}
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (coins[i] & (1 << j)) {
					cnt++;
				}
			}
		}
		minTail = min(minTail, cnt);
		return;
	}

	go(here + 1);
	coins[here] = ~coins[here];
	go(here + 1);
}


int main() {
	string str;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> str;
		int num = 0;
		for (int j = 0; j < N; j++) {
			if (str[j] == 'T') {
				num += pow(2, j);
			}
		}
		coins[i] = num;
	}
	go(0);
	cout << minTail;
	

}