백준 BOJ 14939 - 불 끄기

처음 봤을때는 전구를 두번 켜고끄고 할필요가 없다는 내용을 떠올리고

무지성 브루트포싱을 시도했지만 바로 2^100 TLE

 

나만 모르는 웰논 풀이

윗줄에 대해서 비트마스킹 등으로 브루트포싱을 진행해주면,

그 아랫줄은 윗줄의 상태에 따라서 켜고끄고 여부를 결정할수 있다고 한다.

쭉 순회해가면서 처리하기.

 

구현자체는 그리 어렵진 않았다.

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

14939번: 불 끄기

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

int arr[15][15] = {0};
int tmp[15][15] = {0};
string in;

void flip(int x, int y){
	tmp[x][y] = !tmp[x][y];
	tmp[x-1][y] = !tmp[x-1][y];
	tmp[x+1][y] = !tmp[x+1][y];
	tmp[x][y-1] = !tmp[x][y-1];
	tmp[x][y+1] = !tmp[x][y+1];
	return;
}

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	
	for(int i=0; i<10; i++){
		cin >> in;
		for(int j=0; j<10; j++){
			arr[i][j] = in[j] == '#' ? 0 : 1;
		}	
	}
	
	int cnt;
	int ans = 1e9;
	
	for(int bit=0; bit<1024; bit++){
		
		for(int i=0; i<10; i++) for(int j=0; j<10; j++){
			tmp[i+1][j+1] = arr[i][j];
		}
		
		cnt = 0;
		for(int i=0; i<10; i++){
			if(bit & 1<<i){
				flip(1, i+1);
				cnt++;
			}
		}
		
		for(int i=2; i<=10; i++){
			for(int j=1; j<=10; j++){
				if(tmp[i-1][j] == 1){
					flip(i,j);
					cnt++;
				}
			}
		}
		
		int chk = 0;
		for(int i=1; i<=10; i++) for(int j=1; j<=10; j++) chk += tmp[i][j];
		if(chk == 0) ans = min(ans, cnt);
	}
	if(ans == 1e9) cout << -1;
	else cout << ans;
	return 0;
}

되게 오랜만에 PS잡은거같음....