[BOJ 20161 // C++] 왜 동전은 하나씩만 뒤집는 거야

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

 

이번에 볼 문제는 백준 20161번 문제인 왜 동전은 하나씩만 뒤집는 거야이다.
문제는 아래 링크를 확인하자.

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

 

주어진 동전의 앞면과 뒷면을 나타내는 0과 1을 이용하면 앞의 $K$개의 동전을 $K$자리의 이진수로 항상 변환할 수 있다. 가능한 $2^K$개의 상태에 대하여 그 상태를 만들기 위해 필요한 동전뒤집기의 수를 구하고, 맨 앞자리가 최종결과와 일치하는 경우를 골라 다음 상태로 넘기는 것을 반복해 문제를 DP로 해결하자.

 

같은 구간에 여러 번의 동전뒤집기를 시행할 수도 있음에 유의하자. 예를 들어 5개의 동전이 있고 $K=2$일 때, 모든 동전을 뒤집어야한다면 같은 구간을 적어도 한 번은 골라야 함을 관찰할 수 있다.

 

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

#include <iostream>
#include <queue>
#include <cstring>
#include <utility>
using namespace std;

int N, K, KK;
int A[101], B[101];
int bdist[1024], val[1024], tmp[1024];

void solve1() {
	for (int i = 0; i < N; i++) {
		if (A[i] != B[i]) {
			cout << -1;
			return;
		}
	}
	cout << 0;
}

queue<int> bque;

void solve2() {
	KK = (1 << K);
	bque.push(0);
	bdist[0] = 1;
	while (!bque.empty()) {
		int cur = bque.front(); bque.pop();
		for (int b = 1; b < KK; b <<= 1) {
			int nxt = cur ^ (KK - 1) ^ b;
			if (!bdist[nxt]) bdist[nxt] = bdist[cur] + 1, bque.push(nxt);
		}
	}

	memset(val, 0x3f, sizeof(val));
	int X = 0;
	for (int k = 0; k < K; k++) X = X * 2 + A[k];
	val[X] = 0;
	int b = (KK >> 1);

	for (int L = 0, R = K - 1; R < N; L++, R++) {
		memset(tmp, 0x3f, sizeof(tmp));
		for (int cur = 0; cur < KK; cur++) {
			for (int k = 0; k < KK; k++) {
				if (!bdist[k]) continue;
				int nxt = cur ^ k;
				if ((nxt & b) != (B[L] << (K - 1))) continue;
				nxt = ((nxt << 1) + A[R + 1]) & (KK - 1);
				tmp[nxt] = min(tmp[nxt], val[cur] + bdist[k] - 1);
			}
		}
		swap(val, tmp);
	}
	X = 0;
	for (int k = 0; k < K; k++) {
		X = X * 2 + B[N - K + k + 1];
	}
	
	if (val[X] < 0x3f3f3f3f) cout << val[X];
	else cout << -1;
}

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];

	if (K == 1) solve1();
	else solve2();
}