[백준 BOJ / Python] 1322번 x와 k

문제

x와 k가 주어졌을 때, 다음 식을 만족하는 k번째 y를 구하는 문제이다.

• x + y = x | y

여기서 |는 비트 연산자 OR를 의미한다.

풀이

• x + y와 x | y가 같다는 것은 2진수로 바꾸었을 때, 1의 위치가 서로 다르다는 것을 의미한다. 
  예를 들어 x가 5(101) y가 2(10)이라면 101 + 10 = 101 | 10 = 111로 같다.
  
  
• 이때 y를 구하는 것임으로 x를 기준으로 y를 설명하자면,
  x가 1이면 y는 0을 가지고
  x가 0일 때 y는 1 혹은 0을 가질 수 있다는 것이다.

• k번 째 y는 1 혹은 0이 들어가는 자리를 조절하여 구할 수 있다.
  첫 번째 y는 x가 0인 곳에 1(1)이 들어가면 되고
  두 번째 y는 x가 0인 곳에 2(10)가 들어가면 된다.

 

• 위의 그림에서 검은색으로 된 곳을 잘 살펴보면 해당 자리에 2진 수로 된 자릿수 k가 들어가는 것을 알 수 있다.
  즉 x가 5(101) 일 때,
  첫 번째 y는 2(10)가 되고
  두 번째 y는 8(1000)이 된다.
  
  
• 따라서 뒤에서부터 앞으로 오면서 x가 1일 때는 0, 0일 때는 k 값을 집어넣어 주면 답을 구할 수 있다.

 

알고리즘

1. x와 k를 2진수로 변환하여 리스트에 담는다. (python에서는 2진수로 변환되면 앞에 0b가 붙는다.)
2. x값이 있다면 뒤에서부터 1일 때는 0을 넣어주고, 0일 때는 k 값을 뒤에서부터 넣어준다.
3. 만약 x값이 안 남는다면 k 값을 이어서 붙여준다.
4. 2진수를 다시 10진수로 바꿔준다.

 

Python 코드

x,k = map(int,input().split())
k = list(bin(k)[2:])
x = list(bin(x)[2:])
ans = ""
while k:
    if x:
        a = x.pop()
        if a == "1":
            ans += "0"
        else:
            ans += k.pop()
    else:
        ans += k.pop()

print(int("0b"+ans[::-1],2))

 

문제출처

1322번: X와 K