[백준] 1322: X와 K (Python)

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

import sys

x, k = map(lambda m: list(bin(int(m))[2::]), sys.stdin.readline().split())
y = ''
while k:
    if x and x.pop()=='1':
        y += '0'
    else:
        y += k.pop()
print(int(y[::-1], 2))

두 자연수 X와 K가 주어졌을 때, X+Y==X|Y를 만족하는 K번째로 작은 자연수 Y를 찾는 문제이다. K의 범위가 2,000,000,000보다 작거나 같은 자연수라고 주어졌으므로 전체탐색을 하면 안된다.

1) 아이디어

OR연산과 덧셈의 결과가 같아야 하므로, X와 Y를 AND연산하면 결과값이 0이어야 한다. 따라서 X값을 이진수로 변환했을 때, 비트가 1인 자릿수는 Y값에서 무조건 0이다. 예를 들어 X가 84라고 할 때 다음과 같다.

OR연산이므로 연두색 비트에는 0과 1 모두 들어갈 수 있다. 따라서 답을 구할 때는 연두색 비트만 고려하면 된다. 아래는 X=12일때를 예시로 Y를 나열한 표이다.

2) 풀이

X와 K를 2진수로 변환한 후 LSB부터 규칙에 따라 배열한 후 뒤집는다.