취미로 코딩하기

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

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

https://www.acmicpc.net/problem/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;
}

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

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

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

첫 행의 전구를 건드리고, 앞으로 더 건드리지 않는 상황을 생각해보자. 이 때 첫 행의 전구를 모두 꺼진 상태로 만들려면 둘째 행을 통해 첫째 행을 건드리는 수밖에 없다. 또한 첫 행의 전구가 모두 꺼지게끔 두 번째 행의 전구를 건드리는 방법은 단 한가지만 나온다는 것을 관찰할 수 있다.

이러한 성질은 위 상황 이후 두번째 행과 세번째 행에 대해서도, 나아가 r번째 행과 r+1번째 행에 대해서도 반복적으로 나타나는 점을 관찰하자. 이를 이용하여 문제를 해결할 수 있다.

모든 첫 행의 전구를 건드리는 경우의 수(1024가지)에 대하여 위의 방식대로 전구를 건드려보고 그 결과 모든 전구가 꺼진다면 이 때의 시도횟수를 기록해 그 최솟값을 찾는 방식으로 문제를 해결하자.

각 행의 전구의 상태를 켜짐(1)과 꺼짐(0)으로, 즉 이진수로 비트마스킹하여 정수 하나로 나타내면 문제를 빠르게 해결할 수 있다.

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

#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[11];

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

	for (int i = 0; i < 10; i++) {
		int& x = board[i];
		string s; cin >> s;
		for (auto& l : s) {
			x <<= 1;
			if (l == 'O') x++;
		}
	}

	int ans = 1000000007;
	for (int i = 0; i < 1024; i++) {
		int cnt = count1(i);
		int old = board[0], cur = board[1];
		old ^= i;
		old ^= (i << 1);
		old ^= (i >> 1);
		cur ^= i;
		old &= 1023;
		for (int r = 1; r < 10; r++) {
			cnt += count1(old);
			cur ^= old;
			cur ^= (old << 1);
			cur ^= (old >> 1);
			cur &= 1023;
			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;
}