[Kotlin] 백준 1322 : X와 K

문제 링크 : https://www.acmicpc.net/problem/1322

문제 해설

\(X+Y=X|Y\)가 되는 \(Y\) 중 \(K\)번째 수를 구해야 한다.

 

\(X+Y=X|Y\)가 성립하는 것이 어떤 의미인지 생각해보기 위해 2진수의 경우를 생각해보자.

 

\(X|Y\)는 2개의 2진수 중 하나라도 1인 모든 비트를 1로 만들어주는 연산이다.

 

\(X+Y\)는 아래 그림의 \(101001+1110\)의 경우를 보자.

2개의 2진수 중 하나만 1인 비트만 1이 되고, 둘 다 1인 비트는 받아올림 비트가 발생하면서 0이 된다.

 

여기까지 보면 \(Y\)가 \(X\)에서 0인 비트만 1로 채워나가서 받아올림 비트가 발생하지 않는 수일 때 \(X+Y=X|Y\)가 성립한다는 것을 알 수 있다.

 

그러면 이제 \(K\)번째 \(Y\)는 어떻게 구할 수 있을까?

 

\(X\)에서 0인 비트만 1로 채워나간 수가 \(Y\)이기 때문에 \(X=41,K=6\)인 경우에 대해 생각해보자.

검은 숫자는 X에서 1인 비트이기 때문에 0으로 고정되는 비트, 녹색 숫자는 X에서 0인 비트이기 때문에 유동적으로 변하는 비트이다.

 

여기서 녹색 숫자만 이어서 보면 \(K\)번째 \(Y\)의 녹색 숫자를 이어서 쓴 수가 \(K\)와 같다는 사실을 알 수 있다. 즉 \(K\)번째 \(Y\)는 \(X\)의 1을 모두 0으로 바꾸고, 원래 0인 비트에 \(K\)를 채워넣은 수라는 것을 알 수 있다.

 

원리는 알아냈으니 구현을 해보자.

 

우선 \(X\)와 \(K\)를 2진수 문자열로 변경한다.

val (x, k) = readLine().split(' ').map { it.toInt().toString(2) }

이제 \(X\)의 가장 오른쪽 비트부터 순회를 시작한다.

 

\(X\)의 비트가 1인 경우엔 0을, 0인 경우엔 \(K\)를 최하위 비트(오른쪽 비트)부터 채워나간다. 이 때 \(K\)의 모든 비트를 채워넣었다면 나머지 \(X\)의 비트와 상관없이 모두 0으로 채울 수 있고, leading zero는 모두 무시할 수 있기 때문에 순회를 종료한다.

var index = k.lastIndex
val result = StringBuilder()
for (i in x.lastIndex downTo 0) {
    when (x[i]) {
        '1' -> result.append('0')
        else -> if (index >= 0) result.append(k[index--]) else break
    }
}

\(X\)의 모든 비트를 순회하더라도 \(K\)의 모든 비트를 순회하지 않았을 수도 있다. 이를 위해 지금까지 순회한 \(K\)의 비트 이후부터(index부터) 최상위 비트까지 채워넣는다.

result.append(k.slice(index downTo 0))

마지막으로 result에는 최하위 비트부터 채워넣었기 때문에 상위 비트가 왼쪽으로 갈 수 있도록 뒤집은 후 10진수로 변환하여 출력한다. 이 때 문제에서 정답이 Int 범위를 넘을 수 있다고 했기 때문에 Long 타입으로 변환해준다.

println(result.reversed().toString().toLong(2))

Code

fun main() = with(System.`in`.bufferedReader()) {
    val (x, k) = readLine().split(' ').map { it.toInt().toString(2) }
    var index = k.lastIndex
    val result = StringBuilder()
    for (i in x.lastIndex downTo 0) {
        when (x[i]) {
            '1' -> result.append('0')
            else -> if (index >= 0) result.append(k[index--]) else break
        }
    }
    result.append(k.slice(index downTo 0))
    println(result.reversed().toString().toLong(2))
}