백준 - 빌런 호석 - 22251 - swift

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

22251번: 빌런 호석

 

 

문제 유형은 구현, 완전탐색 또는 비트마스킹이 될 수 있다.

 

하나의 문제에서 다양한 접근법이 가능하므로 

정말 좋은 문제인 것 같다. 

어떻게 이런 문제를 만드는지 정말 대단하다. 

 

내 기준에서는 조금 난이도가 있었다

 

내 접근법 

우선 처음 접근법( 구현 + 완전탐색 ) 은 다음과 같았다. 

 

하나의 디스플레이에 0부터 9까지 숫자를 표현할 수 있고, 각 숫자마다 필요한 LED가 다르다.  

또, 각 디스플레이마다  LED는 최대 7개이다. 

호석이는 1부터 최대 P개까지 LED를 반전시킬 수 있다. 

그러므로 각 숫자마다 최대 7개까지 반전시킬 수 있다.

• possibles [ x ] [ y ] = 숫자가 x일때, 숫자 y가 되기 위한 최소 반전횟수 로 정했다.
• 디스플레이는 최대 K개 (6개)인데, 이중에서 적절히 반전시킬 LED개수들을 각 디스플레이마다 나눠줘야한다. 하지만 이렇게 접근하면 굉장히 문제가 어려워지고, 고려할게 많아진다. 
• 그러므로, 각 디스플레이마다 LED개수를 부여하지 않고,  각 디스플레이마다 현재 숫자에서 다음숫자로 되기 위한 값들을 모두 더한 다음 P보다 작거나 같으면 된다. 
• 이걸 구현하기 위해서는,  하나의 디스플레이에 최대 LED가 7개이므로, 위에서부터 아래로 검은부분은 1, 흰색은 0으로,  배열로 표시했다. 즉  0인 경우는  [1,1,1,0,1,1,1] 로 표시했다. 순열로, 1부터 7까지 모두 반전가능한 경우를 찾고, 숫자로 표시하고, 최소 횟수를 저장해나갔다.

 

그래서 각 숫자마다 1부터 7개까지 반전시켜 얻을 수 있는 숫자들을 모두 구한다. 

 

그리고, 엘레베이터 층은 최대 N층까지인데, 이는 최대 999,999 층까지다. 

즉 1부터 N층까지 모두 탐색해도 시간안에 충분히 계산가능하다. 

그러므로, 1부터 N층까지 모두 탐색하면서,

탐색하는 숫자가 현재 멈춰있는 X층으로 변환될 수 있는 숫자인지 탐색했다. 

 

이렇게 해서 겨우 맞출 수 있었다.

 

 

비트마스킹 접근법 

하지만 다른 분의 코드가 굉장히 짧았는데... 그 이유는.. 바로 비트마스킹!

정말 머리가 띵했다. 한동안 코딩테스트를 손을 놔붜리니 감각을 잃어버렸나보다. 

나도 비트마스킹처럼 숫자를 1과 0으로만 표현하도록 했는데, 허허 비트마스킹까지 생각 못했다.

 

위에서 숫자들을 배열로 표현한 것 처럼 ( 어떤식으로 표현하든 상관없다. 그저 7개의 비트로 표현하면 된다 )

그대로 그걸 비트로 계산하는거다. 

 

즉 0 은 1110111,  1은 0010010   

이를 다시 10진수로 나타내면, 각각  119, 18 이 된다 

 

자 그럼, 0에서 1이 되려면 몇번의 반전이 필요할까? 

매우 간단하게 XOR연산을 이용하면 된다.

119 ^ 18 을 구하면 되는데

1  1 1 0 1 1 1

0 0 1 0 0 1 0 

위와 같이 XOR연산하면 딱 필요한 반전들을 찾을 수 있다.

그럼 118 ^ 18 =  2진수로 1100101 이 나오게 되고, 

이를 1의 개수들만 세주면 반전의 횟수가 나온다

 

그러므로, 위의 접근법처럼, 1부터 N까지 모두 탐색하면서, 

각각 비트연산을 통해서 반전의 횟수 합을 구하여 P보다 작거나 같은 경우들만 카운팅 하면 된다. 

 

 

비트마스킹 코드 

import Foundation
let inp = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = inp[0], K = inp[1], P = inp[2], X = inp[3]
var beat = [119, 18, 93, 91, 58, 107, 111, 82, 127, 123]

func makeFull(_ val: Int ) -> [Int] {
    var list = [Int]()
    var x = 10
    var val = val
    while x < N*10 {
        list.append(val%x/(x/10))
        val -= val%x
        x *= 10
    }
    return list
}

let nums = makeFull(X)
var ans = 0

for i in 1...N {
    if X == i { continue }
    let target = makeFull(i)
    if  zip(nums,target).reduce(0, {
        var n = beat[$1.0]^beat[$1.1]
        var c = 0
        while n > 0 {
            n -= n & -n
            c += 1
        }
        return $0 + c
    }) <= P {
        ans += 1
    }
}
print(ans)

 

 

처음 접근법 코드 

import Foundation
let inp = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = inp[0], K = inp[1], P = inp[2], X = inp[3]

let dictNum: [[Int]: Int] = [
    [1,1,1,0,1,1,1]: 0,
    [0,0,1,0,0,1,0]: 1,
    [1,0,1,1,1,0,1]: 2,
    [1,0,1,1,0,1,1]: 3,
    [0,1,1,1,0,1,0]: 4,
    [1,1,0,1,0,1,1]: 5,
    [1,1,0,1,1,1,1]: 6,
    [1,0,1,0,0,1,0]: 7,
    [1,1,1,1,1,1,1]: 8,
    [1,1,1,1,0,1,1]: 9
]

var dictArr = [Int: [Int]]()
dictNum.forEach { dictArr[$0.value] = $0.key }
var possibles = Array(repeating:Array(repeating: Int.max, count: 10), count: 10)

func change(_ mx: Int, _ num: Int ) {
    var possible = Array(repeating: Int.max, count: 10)
    possible[num] = 0
    
    func permutation(_ count: Int, list: [Int] ) {
        if list.count == count {
            var val = dictArr[num]!
            list.forEach {
                val[$0] ^= 1
            }
            if let new = dictNum[val] {
                possible[new] = min(possible[new], count)
            }
            return
        }
        for i in 0..<7 {
            if !list.contains(i) {
                permutation(count, list: list+[i])
            }
        }
    }
    for i in 1...mx {
        permutation(i, list: [])
    }
    possibles[num] = possible
}

for i in 0...9 {
    change(7, i)
}

var numbers = String(X).reversed().map{Int(String($0))!}

while numbers.count < K {
    numbers.append(0)
}
var ans = 0
for i in 1...N {
    var indices = [Int]()
    var x = 10
    var num = i
    while x < N*10 {
        indices.append(num%x/(x/10))
        num -= num%x
        x *= 10
    }
    var isCan = true
    var sum = 0
    zip(indices, numbers).forEach {
        let need = possibles[$1][$0]
        if need == Int.max {
            isCan = false
        } else {
            sum += need
        }
    }
    if isCan, sum <= P, i != X {
        ans += 1
    }
}
print(ans)