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

Problem : https://www.acmicpc.net/problem/1948

1948번: 임계경로

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:13:58

 

---

 

문제 설명

 

 

두 자연수 X와 K가 주어진다. 그러면, 다음 식을 만족하는 K번째로 작은 자연수 Y를 찾아야 한다.

X + Y = X | Y

|는 비트 연산 OR이다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄에 X + Y = X | Y를 만족하는 K번째 작은 Y를 출력한다. 정답은 231-1 보다 클 수도 있다.

 

입력 예시

 

5 1

 

출력 예시

 

2

 

 

---

 

풀이

 

X + Y = X | Y 가 성립하려면, X, Y를 2진법으로 나타내었을 때 각 자릿수에 대해...

 

• X(n) = 1일때 Y(n) = 0
• X(n) = 0일때 Y(n) = 0 or 1

 

이 성립된다. bitwise OR은 자리올림 carry가 발생하지 않기 때문에, 덧셈에서 자리올림이 발생하는 유일한 경우인 1 + 1이 모든 자릿수에서 발생하지 않을 때만이 위 등식이 성립한다. 즉 X가 0인 자릿수를 모두 구하여, 경우의 수에 따라 Y를 계산하면 된다.

 

 

풀이 코드

x, k = map(int, input().split())
length = len(bin(x)[2:])
cnt = 1 << bin(x)[2:].count('0')

ans = 0
if k >= cnt :
  ans = (1 << length)*(k // cnt)
  k %= cnt

idx = 0
for i in range(length) :
  if not x & (1 << i) :
    if k & (1 << idx) :
      ans += (1 << i)
    idx += 1
print(ans)

풀이 완료!