[BOJ] 백준 22251번: 빌런 호석(C++)/BitMasking

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

22251번: 빌런 호석

류호석배 알고리즘 코딩 테스트는 문제 퀄리티가 정말 좋아서 자주 푸는데 이번에도 새로운 코딩 테스트가 열렸다

실시간으로 참여할까 했지만 평일에 5시간이나 백준 문제를 풀면 너무 지칠 것 같아서ㅠ

천천히 풀어보려고 한다

 

이 문제는 특이하게 숫자 -> 숫자로 변환하는 과정에서 비트마스킹을 사용했다

아래의 그림처럼, 5를 3으로 바꾸기 위해서는 오른쪽 위의 LED를 켜고 왼쪽 위의 LED를 꺼야해서 2회의 반전이 필요하다

나는 각각의 위치에 대해 번호를 매기고 LED가 켜져있으면 1, 꺼져있으면 0으로 해서 0~9까지의 숫자들을 매핑해주고

이중 for문을 이용해 해당 숫자들을 XOR 연산 해주면서 다른 bit의 개수를 세어줬다

이후의 과정은 dfs를 이용한 기본적인 풀이방식이므로 패스 ~~

#include <cstdio>
#include <math.h>
#include <string>
using namespace std;

int n, k, p, x;
int arr[10][10] = { 0 };
string str;

int func(int dep, int cnt) {
	if (dep >= str.length()) {
		if (stoi(str) == x)return 0;
		if (stoi(str) <= n && stoi(str) >= 1) return 1;
		return 0;
	}

	int sum = 0;
	int cur = str[dep] - '0';
	for (int i = 0; i < 10; i++) {
		if ((cur != i) && (arr[cur][i] <= cnt)) {
			str[dep] = i + '0';
			sum += func(dep + 1, cnt - arr[cur][i]);
			str[dep] = cur + '0';
		}
		if (cur == i)sum += func(dep + 1, cnt);
	}
	return sum;
}

int main() {
	int num[] = { 0b1111110, 0b0110000, 0b1101101, 0b1111001, 0b0110011, 0b1011011, 0b1011111, 0b1110000, 0b1111111, 0b1111011 };
	scanf("%d%d%d%d", &n, &k, &p, &x);

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			int k = num[i] ^ num[j];
			while (k != 0) {
				if (k & 1)arr[i][j]++;
				k >>= 1;
			}
		}
	}

	str = to_string(x);
	while (str.length() < k)str.insert(str.begin(), '0');
	printf("%d", func(0, p));

}