[백준] No.1322 - X와 K (C++, 비트마스크)

문제

 

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

1322번: X와 K

 

 

풀이

 

solved.ac 난이도: Gold 4

 

X + Y = X | Y 를 만족시키는 K번째로 작은 자연수 Y를 찾는 문제.

 

조금만 생각해보면 X+Y의 값이 X | Y 과 같기 위해서는 X와 Y의 비트들 중에서 1이 서로 겹치게 등장하면 안 된다는 것을 알 수 있다.

단순히 브루트포스로 해결하려 하면 X + Y = X | Y인 Y값을 1부터 K번째 수가 등장할 때까지 반복해야 하는데

K는 최대 2,000,000,000이므로 시간 안에 해결하는 것은 불가능하다.

 

따라서 비트마스크를 이용하여 K번째 수를 구하는 방식으로 풀어보자.

K번째 수는 X의 최하위 비트(least significant bit, LSB)에서 부터 올라가면서 0이 등장하는 횟수로 구할 수 있다.

예를 들어 X = 101001일 때, 5번째 Y값을 구해보자.

 

k=1 (001)

X = 101001

Y = 000010

 

k=2 (010)

X = 101001

Y = 000100

 

k=3 (011)

X = 101001

Y = 000110

 

k=4 (100)

X = 101001

Y = 010000

 

k=5 (101)

X = 101001

Y = 010010

.

.

.

 

X의 비트중에서 0에 해당하는 부분의 비트는 색을 칠해두었다.

알아채셨는지 모르겠지만, X의 0에 해당하는 부분만 Y의 값에서 확인하면 K의 2진수 표현과 정확히 일치한다.

즉, K번째 Y값을 구하기 위해서는 X에서 0에 해당하는 부분에만 K의 2진수 표현 값을 집어넣으면 된다.

 

 

해당 풀이를 구현하기위해 X에서 0의 등장 개수를 세는 zero_cnt, 현재 비트의 위치를 기록하는 order를 사용했다.

order를 증가시키면서, 0의 개수(zero_cnt)로 만들수 있는 최댓값 (1 << zero_cnt)-1 보다 K가 작다면 더 이상 0의 개수를 세지 않고 break해준다.

 

 

ll zero_cnt =0, order;
for(order=0;  ; ++order){
  if(!(X & ((ll)1<<order) )){ // 해당order의 bit가 0인 경우
    ++zero_cnt;
    if( ((ll)1 << zero_cnt)-1 >= K)
      break;
  }
}

 

이제 Y의 값을 구해주자.

Y값은 X에서 0이 등장할 때마다 현재 0의 개수 (zero_cnt)로 중에서 최상위 비트(most significant bit, msb)만 1로 만든 값  (1 << (zero_cnt-1))보다 K가 크거나 같다면, if((1 << (zero_cnt-1)) <= K)

 

Y의 값의 현재 비트 위치(order)에 1을 저장해준다.

Y |= (1<<order);

 

이제 K = K - (1 << (zero_cnt-1))를 해주어

나머지 0들에서 K값을 구해주면 된다.

 

 

while(order>=0 && zero_cnt>0 && K>0){
  if(!(X & ((ll)1<<order) )){
      
    if(((ll)1 << (zero_cnt-1)) <= K){
      Y |= ((ll)1<<order);
      K = K - ((ll)1 << (zero_cnt-1));
    }
 
    --zero_cnt;
  }
  --order;
}

 

또한 추가적으로 고려해야 하는 것이 있다.

정답은 int형의 범위를 벗어날 수 도 있으니 연산에 사용되는 값들은 모두 long long형으로 선언해주자.

 

 

코드