백준 22251 빌런 호석 c++, Kotlin (완전탐색, 비트마스킹)

문제 출처 : https://www.acmicpc.net/problem/22251

22251번: 빌런 호석

문제

치르보기 빌딩은 1층부터 N층까지 이용이 가능한 엘리베이터가 있다. 엘리베이터의 층수를 보여주는 디스플레이에는 최대 K 자리의 수가 보인다. 수는 0으로 시작할 수도 있다. 0부터 9까지의 각 숫자가 디스플레이에 보이는 방식은 아래와 같다. 각 숫자는 7개의 표시등 중의 일부에 불이 들어오면서 표현된다.

예를 들어 K=4인 경우에 1680층과 501층은 아래와 같이 보인다.

                  

빌런 호석은 치르보기 빌딩의 엘리베이터 디스플레이의 LED 중에서 최소 1개, 최대 P개를 반전시킬 계획을 세우고 있다. 반전이란 켜진 부분은 끄고, 꺼진 부분은 켜는 것을 의미한다. 예를 들어 숫자 1을 2로 바꾸려면 총 5개의 LED를 반전시켜야 한다. 또한 반전 이후에 디스플레이에 올바른 수가 보여지면서 1 이상 N 이하가 되도록 바꿔서 사람들을 헷갈리게 할 예정이다. 치르보기를 사랑하는 모임의 회원인 당신은 호석 빌런의 행동을 미리 파악해서 혼쭐을 내주고자 한다. 현재 엘리베이터가 실제로는 X층에 멈춰있을 때, 호석이가 반전시킬 LED를 고를 수 있는 경우의 수를 계산해보자.

입력

 N, K, P, X 가 공백으로 주어지고 첫째 줄에 주어진다.

출력

호석 빌런이 엘리베이터 LED를 올바르게 반전시킬 수 있는 경우의 수를 계산해보자.

제한

•  1≤X≤N<10^K 
•  1≤K≤6 
•  1≤P≤42

풀이

우선 0,1,2,3,4,5,6,7,8,9를 디스플레이 화 시키면

0 = "1110111",
1 = "0010010",
2 = "1011101",
3 = "1011011",
4 = "0111010",
5 = "1101011",
6 = "1101111",
7 = "1010010",
8 = "1111111",
9 = "1111011"

가 된다.

1은 디스플레이에 led가 들어온 것을 의미하고 0 은 디스플레이에 led가 꺼짐을 의미한다.

이후, n과 x를 자릿수 k에 맞게 디스플레이 화 하고,

최대 p개의 led 반전으로 만들 수 있는 n 이하의 숫자를 세면 된다.

기존에 있는 층인 x와는 다른 층을 만들어야 하니, 만든 수가 x인 경우는 빼주고, 0층인 경우도 빼준다.

본인은 dfs를 이용해 자릿수가 k라 할 때, k 개의 자리에 들어갈 수 있는 값 0~9를 모두 검사하였고,

결과를 resultSet에 저장하였다.

그래서 탐색 범위가 너무 많았고, 결과 또한 많았기 때문에 메모리, 시간 측면에서 효율적이지 않은 코드이다.

비트 마스킹 풀이도 있지만 본인은 비트 마스킹을 공부하진 않았기 때문에 스킵하고

아래 코드를 내일 리팩토링해서 오겠다! 

 

리팩토링한 코드가 3번 코드이다.

시간 차이가 어마어마하다.

 

비트 마스킹을 이용한 풀이인데, 디스플레이를 0b~~를 이용해 2진수 형태의 Int 타입으로 저장한다.

이후 i에서 j로 바꾸는데 필요한 반전 수를 미리 모두 저장해놓고, 2중 for문으로 x -> 1부터 n까지 바꿀 수 있는 수의 개수를 출력한다.

i에서 j로 바꾸는데 필요한 반전 수는 Integer.bitCount(Int)로 쉽게 구할 수 있다.(반복문에 쉬프트 연산으로 직접 구할 수도 있다.)

비트 마스킹만 알면 더 간단해진다!

 

코드1(c++, dfs,set)

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

unordered_set<string> resultSet;
//2진수 스트링으로 0~9를 저장
string numString[10] = {
	"1110111",
	"0010010",
	"1011101",
	"1011011",
	"0111010",
	"1101011",
	"1101111",
	"1010010",
	"1111111",
	"1111011"
};

//void dfs(idx : Int, result : String, strN : String, p : Int, k : Int, strX : String) {
void dfs(int idx, string result, string strN, int p, int k, string strX) {
	if (idx == k) {
		//구한 결과물들 n보다 작은지 검사
		if (result <= strN)
			resultSet.insert(result);
		return;
	}
	//0부터 9까지 변환시켜보기
	for (int i = 0; i < 10; i++) {
		int cnt = 0;
		for (int j = 0; j < 7; j++) {
			if (numString[strX[idx] - '0'][j] != numString[i][j]) {
				cnt++;
			}
		}
		//남은 변환 횟수로 바꿀 수 있다면
		//안 바꾸는 경우는 cnt0이므로 이 안에 포함
		if (cnt <= p) {
			dfs(idx + 1, result + to_string(i), strN, p - cnt, k, strX);
		}
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int k, p;
	string n,x;
	cin >> n >> k >> p >> x;
	
	string startStr = "";
	for (int i = n.length(); i < k;i++) {
		n = '0' + n;
		startStr += '0';
	}
	for (int i = x.length(); i < k;i++) {
		x = '0' + x;
	}
	string zeroStr = "";
	for (int i = 0; i < k; i++) {
		zeroStr += '0';
		}
	//n과 x를 자릿수에 맞게 0추가
	dfs(startStr.length(), startStr, n, p, k, x);
;		int answer = resultSet.size();
		if (resultSet.find(zeroStr) != resultSet.end()) {
			answer--;
		}
	if (resultSet.find(x) != resultSet.end()) {
		answer--;
	}
	//현재 수인 x와 같은 것도 빼주기
	//0층인 경우도 빼주기
	cout << answer;
	return 0;
}

코드2(Kotlin, dfs, set)

import java.util.*
//1<=x<=n<=10^k
//1<=k<=6
//1<=p<=42
//n 최대 수 p 최대 반전 수 k 자릿수 x 현재 수

val resultSet = mutableSetOf<String>()
//2진수 스트링으로 0~9를 저장
val numString = arrayOf(
    "1110111",
    "0010010",
    "1011101",
    "1011011",
    "0111010",
    "1101011",
    "1101111",
    "1010010",
    "1111111",
    "1111011"
)

fun dfs(idx : Int,result : String,strN : String, p : Int, k : Int, strX : String){
    if(idx==k){
        //구한 결과물들 n보다 작은지 검사
        if(result<=strN)
        resultSet.add(result)
        return
    }
    //0부터 9까지 변환시켜보기
    for(i in numString.indices){
        var cnt=0
        for(j in 0 until 7){
            if(numString[Character.getNumericValue(strX[idx])][j]!=numString[i][j]) {
                cnt++
            }
        }
        //남은 변환 횟수로 바꿀 수 있다면
        //안 바꾸는 경우는 cnt0이므로 이 안에 포함
        if(cnt<=p) {
            dfs(idx + 1, result + i.toString(), strN, p - cnt, k, strX)
        }
    }

}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,k,p,x) = br.readLine().split(' ').map{it.toInt()}
    var strN = n.toString()
    var strX = x.toString()
    var startStr = ""
    for(i in strN.length until k){
        strN ='0'+strN
        startStr+='0'
    }
    for(i in strX.length until k){
        strX = '0'+strX
    }
    var zeroStr = ""
    for(i in 0 until k){
        zeroStr+='0'
    }
    //n과 x를 자릿수에 맞게 0추가
    dfs(startStr.length,startStr,strN,p,k,strX)
    var answer = resultSet.size
    if(resultSet.indexOf(zeroStr)!=-1){
        answer--
    }
    if(resultSet.indexOf(strX)!=-1){
        answer--
    }
    //현재 수인 x와 같은 것도 빼주기
    //0층인 경우도 빼주기
    write("$answer")
    close()
}

코드3(Kotlin, 2중 for문, 비트 마스킹)

val br = System.`in`.bufferedReader()

//1<=x<=n<=10^k
//1<=k<=6
//1<=p<=42
//n 최대 수 p 최대 반전 수 k 자릿수 x 현재 수

val cntArr = Array(10){IntArray(10)}
var answer=0
val display = arrayOf(
    0b1110111,
    0b0010010,
    0b1011101,
    0b1011011,
    0b0111010,
    0b1101011,
    0b1101111,
    0b1010010,
    0b1111111,
    0b1111011
)

fun main() = with(System.out.bufferedWriter()){
    val (n,k,p,x) = br.readLine().split(' ').map{it.toInt()}

    for(i in 0 until 10){
        for(j in 0 until 10){
            cntArr[i][j] = Integer.bitCount(display[i] xor display[j])
        }
    }
    for(i in 1 .. n){
        var from = x
        var to = i
        var cnt=0
        for(j in 0 until k){
            cnt+=cntArr[from%10][to%10]
            from/=10
            to/=10
        }
        if(cnt>0 && cnt<=p)answer++
    }
    write("$answer")
    close()
}

코드4(Kotlin, 비트 마스킹)

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
/*
* n = 최대 층
* k = 자릿수
* p = 최대 반전 수
* x = 현재 층
* */
val numBits = arrayOf(
    0b1110111, //0
    0b0010001, //1
    0b0111110, //2
    0b0111011, //3
    0b1011001, //4
    0b1101011, //5
    0b1101111, //6
    0b0110001, //7
    0b1111111, //8
    0b1111011, //9
)

var answer =0

fun backTracking(n: Int, k: Int, p: Int, x: StringBuilder, idx: Int, result: Int) {
    if (idx == k) {
        if (result != 0) {
            answer++
        }
        return
    }
    for (i in 0..9) {
        val diff = (numBits[Character.getNumericValue(x[idx])] xor numBits[i]).countOneBits()
        if (p - diff < 0) continue
        val next = result * 10 + i
        if (next > n) continue
        backTracking(n, k, p - diff, x, idx + 1, next)
    }
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, k, p, x) = getIntList()

    val sb = StringBuilder(x.toString()).reverse().apply {
        while (this.length < k) {
            append('0')
        }
        reverse()
    }
    //solve
    backTracking(n, k, p, sb, 0, 0)
    //output
    write("${answer - 1}")
    close()
}