[BOJ 14927 // C++] 전구 끄기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14927번 문제인 전구 끄기이다.
문제는 아래 링크를 확인하자.

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

14927번: 전구 끄기

14939번 문제에서 변의 길이가 주어지는 형태로 바뀐 문제이다.

 

전체적인 풀이는 위의 문제와 같으니 위 글을 참고하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int count1(int x) {
	int ret = 0;
	while (x) {
		if (x & 1) ret++;
		x >>= 1;
	}

	return ret;
}

int board[19];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int& x = board[i];
		for (int j = 0; j < N; j++) {
			x <<= 1;
			int p; cin >> p;
			x += p;
		}
	}

	int ans = 1000000007;
	int iterend = (1 << N);
	int xornum = iterend - 1;
	for (int i = 0; i < iterend; i++) {
		int cnt = count1(i);
		int old = board[0], cur = board[1];
		old ^= i;
		old ^= (i << 1);
		old ^= (i >> 1);
		cur ^= i;
		old &= xornum;
		for (int r = 1; r < N; r++) {
			cnt += count1(old);
			cur ^= old;
			cur ^= (old << 1);
			cur ^= (old >> 1);
			cur &= xornum;
			int tmp = old ^ board[r + 1];
			old = cur;
			cur = tmp;
		}
		if (old == 0) ans = min(ans, cnt);
	}

	if (ans < 1000000007) cout << ans;
	else cout << -1;
}