[백준] X와 K(1322)

문제 링크 : [백준] X와 K(1322)

문제 설명

N과 K가 주어졌을 때,
N + Y = N | Y
위 수식이 성립하는 Y 중 K번째로 작은 Y를 출력하세요.

입력

N K(1<=N,K<=2,000,000,000)

5 1

출력

2

카테고리

#수학 #비트마스크

시간 복잡도 상한

O(logN)까지 가능합니다.

해결 방법

1. N+Y=N|Y가 성립하려면, N과 Y를 2진수로 표시했을 때, 서로 같은 자리수가 동시에 1인 자리가 있으면 안됩니다.
2. 같은 자리가 동시에 1이라면
   2-1. +일 경우, 그 자리가 0으로 변경되고, 다음 자리수가 1 커집니다.
   2-2. |일 경우, 그 자리의 수도 변경이 되지 않고, 자리 올림도 발생하지 않습니다.
3. 위 두 경우의 차이 때문에, 같은 자리수가 동시에 1인 경우를 제외한 수들 중에서 K번째로 작은 수를 찾으면 됩니다.
4. 1부터 K까지 순서대로 탐색하면서 3의 내용을 처리하다 보면 K의 최대가 20억이기 때문에 타임아웃이 발생합니다. 따라서 K번째 수를 빨리 구해야합니다.
5. 1<<X 비트를 켜는데 2^X개의 경우들이 존재합니다.
6. 1<<X가 K보다 작거나 같다면, 반드시 해당 비트를 켜야합니다.
7. 6에서 해당 비트를 켰다면, 이미 2^X개의 작은 수들을 사용했기 때문에 K를 2^X 만큼 빼줍니다.
8. 6, 7을 큰수에서 작은수 방향으로 반복하여 켤 비트를 확인합니다.
9. 단, 3번을 처리해야 합니다.
   9-1. N의 이진수 중, 켜고자 하는 비트수보다 작은 자리에서 켜진 비트가 있으면 그 비트는 경우의 수에 포함되지 않기 때문에, 카운팅 대상에서 제외하여 X값을 보장하면서 수를 세면 됩니다.

시간복잡도

최대 64*64

코드

#include<cstdio>
int n,k,d[63],i,j,t;
long long a;
int main(){
    scanf("%d%d",&n,&k);
    for(;i<32;i++)d[i]=!!(n&(1<<i));
    for(i=62;i>=0;i--){
        if((1ll<<i)<=k){
            t=i;
            for(j=0;j<=t;j++)t+=d[j];
            k-=(1ll<<i);
            a+=(1ll<<t);
        }
    }
    printf("%lld",a);
}