BOJ 1285 - 동전 뒤집기

문제

n x n으로 표현되는 \(N^2\)개의 동전들의 상태가 주어진다. (\(N\le 20\))

한 행이나 한 열의 동전들을 모두 뒤집는 작업들을 수행해서 나올 수 있는, 뒷면이 위를 향하는 동전이 최소일 때 그 개수를 구하는 문제이다.

풀이

크기 n인 벡터 안에 각각 n비트을 저장하면 n x n의 상태를 표현할 수 있다.
나는 행을 기준으로, 벡터 한 칸에 한 행을 저장했다.

n이 충분히 작기 때문에 행에 대해서는 뒤집는 모든 경우의 수를 탐색할 수 있다.(\(2^{20}=1048576\))
이때 한 열에서의 뒷면인 동전 수를 세고 n에서 빼면 그 열을 뒤집었을 때 뒷면의 개수를 구할 수 있다.

첫 번째 행부터 시작해서 재귀적으로 모든 경우의 수를 탐색하는 방법으로 구현할 수 있다.

소스코드

#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef vector<int> vi;

int n, all1=0;

int solve(vi& rows, int row){
	if(row==n){
		int cnt=0;
		for(int i=0;i<n;i++){
			int tcnt=0;
			for(int j=0;j<n;j++){
				tcnt+=!(rows[j]&(1<<(n-i-1)));
			}
			cnt+=(tcnt>n/2)?n-tcnt:tcnt;
		}
		return cnt;
	}

	int nrow=solve(rows, row+1), yrow;
	rows[row]=rows[row]^all1;
	yrow=solve(rows, row+1);
	return (nrow>yrow)?yrow:nrow;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<n;i++) all1|=1<<i;
	string s;
	vi rows(n, 0);
	
	for(int i=0;i<n;i++){
		int cnt=0;
		cin>>s;
		for(int j=0;j<s.length();j++){
			if(s[j]=='H') rows[i]|=(1<<(n-j-1));
		}
	}
	cout<<solve(rows, 0);
	return 0;
}

풀고나서

• constructive하게 풀려고 시도했지만, 알 수 없었다.
• bitset 헤더를 이용하면 cout<<bitset<8>(val);과 같이 원하는 비트수로 값을 출력할 수 있다.
• 스트링을 받을 때 getline(cin, s)를 이용하는 것보다 cin>>s로 받는 게 훨씬 예외처리가 편하다. 예제들은 잘 실행되었지만, 저 두 개 차이로 백준에서는 입력이 제대로 수행되지 않았다.