C++로 비트 OR 연산 결과가 K가 되는 N개의 서로 다른 숫자 찾기

문제 개요

두 정수 N과 K가 주어졌을 때, 이 숫자들을 비트 OR(bitwise OR) 연산했을 때 결과가 정확히 K가 되는 N개의 서로 다른 정수를 찾는 것이 목표입니다. 만약 가능한 답이 존재하지 않는다면 -1을 출력해야 합니다.

입력 및 출력 예시

입력:

N = 4, K = 6

출력:

6 0 1 2

입력:

N = 11, K = 6

출력:

-1

두 번째 예시에서는 조건을 만족하는 서로 다른 11개의 정수를 만들 수 없으므로 해답이 존재하지 않습니다.

접근 방법

여러 숫자의 비트 OR 결과가 K가 되려면, K에서 비트가 0인 자리는 모든 숫자에서 반드시 0이어야 한다는 점을 활용합니다.
따라서 우리가 자유롭게 값을 바꿀 수 있는 자리는 K에서 비트가 1인 위치뿐입니다. 이 1인 비트의 개수를 Bit_K라고 합시다.
Bit_K개의 비트로는 최대 pow(2, Bit_K)개의 서로 다른 숫자를 만들 수 있습니다. 하나의 숫자를 K 자체로 사용하면, 나머지 N-1개의 숫자는 'K에서 0인 비트는 모두 0으로 유지하고, 나머지 Bit_K개의 비트 자리에는 K가 아닌 값들의 조합'을 배치하는 방식으로 만들 수 있습니다.
결론적으로 pow(2, Bit_K) < N이라면 조건을 만족하는 답을 찾을 수 없으므로 -1을 출력합니다.

C++ 구현 예제

// 위 접근 방식의 C++ 구현
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX1 32
ll pow2[MAX1];
bool visited1[MAX1];
vector<int> ans1;

// MAX까지의 모든 2의 거듭제곱을
// 미리 계산하는 함수
void power_2(){
    ll ans1 = 1;
    for (int i = 0; i < MAX1; i++) {
        pow2[i] = ans1;
        ans1 *= 2;
    }
}
// x의 1인 비트(set bit) 개수를
// 반환하는 함수
int countSetBits(ll x1){
    // 1인 비트의 개수를 저장
    int setBits1 = 0;
    while (x1 != 0) {
        x1 = x1 & (x1 - 1);
        setBits1++;
    }
    return setBits1;
}
// K에서 0인 비트 자리를 모두 0으로
// 고정한 상태로 num을 답에 추가하는 함수
void add(ll num1){
    int point1 = 0;
    ll value1 = 0;
    for (ll i = 0; i < MAX1; i++) {
        // 비트 i가 K에서 0인 경우
        if (visited1[i])
            continue;
        else {
            if (num1 & 1) {
                value1 += (1 << i);
            }
            num1 /= 2;
        }
    }
    ans1.push_back(value1);
}
// 비트 OR가 K가 되는 N개의 서로 다른
// 숫자를 찾아 출력하는 함수
void solve(ll n1, ll k1){
    // K 자체를 첫 번째 숫자로 선택
    ans1.push_back(k1);
    // K의 1인 비트 개수 구하기
    int countk1 = countSetBits(k1);
    // N개의 서로 다른 정수를
    // 만들 수 없는 경우
    if (pow2[countk1] < n1) {
        cout << -1;
        return;
    }
    int count1 = 0;
    for (ll i = 0; i < pow2[countk1] - 1; i++) {
        // K에서 0인 비트를 모두 0으로
        // 고정한 후 i를 답에 추가
        add(i);
        count1++;
        // N개의 서로 다른 숫자가
        // 생성되면 종료
        if (count1 == n1)
            break;
    }
    // 생성된 숫자들을 출력
    for (int i = 0; i < n1; i++) {
        cout << ans1[i] << " ";
    }
}
// 드라이버 코드
int main(){
    ll n1 = 4, k1 = 6;
    // 모든 2의 거듭제곱을
    // 미리 계산
    power_2();
    solve(n1, k1);
    return 0;
}

실행 결과

6 0 1 2

동작 원리 요약

위 코드는 먼저 2의 거듭제곱 값을 미리 계산해 둔 뒤, K의 1인 비트 개수를 세어 2^Bit_K ≥ N 조건을 확인합니다. 조건을 만족하면 K 자체를 첫 번째 숫자로 넣고, 0부터 차례대로 숫자를 살펴보며 K에서 0인 비트 자리를 강제로 0으로 만든 값을 답에 추가합니다. 이렇게 하면 모든 숫자의 OR 결과가 K를 벗어나지 않으면서, 서로 다른 N개의 숫자를 안정적으로 생성할 수 있습니다.