C++로 XOR을 최대화하기 위해 제거해야 할 요소의 최소 개수 구하기

문제 설명

자연수 N이 주어집니다. 1부터 N까지의 연속된 숫자들 가운데 일부를 제거했을 때, 남은 숫자들의 XOR(배타적 논리합) 값이 최대가 되도록 만들어야 합니다. 이때 제거해야 하는 숫자의 최소 개수를 구하는 것이 이 문제의 목표입니다.

알고리즘

모든 조합을 일일이 시도하는 대신, N의 값에 따라 답이 규칙적으로 결정된다는 점을 활용하면 매우 효율적으로 해결할 수 있습니다.

1. n이 1 또는 2라면 어떤 요소도 제거할 필요가 없습니다. 따라서 답은 0입니다.
2. n보다 크거나 같은 2의 거듭제곱 수를 찾습니다. 이 값을 nextNumber라고 하겠습니다.
   2.1. n == nextNumber 또는 n == (nextNumber - 1)이라면 답은 1입니다.
   2.2. n == (nextNumber - 2)라면 답은 0입니다.
3. 그 외의 경우, n이 짝수이면 답은 1이고 홀수이면 답은 2입니다.

동작 원리

XOR 연산은 동일한 비트가 두 번 등장하면 서로 상쇄되는 성질을 가집니다. 1부터 N까지의 XOR 값은 N을 4로 나눈 나머지에 따라 일정한 패턴을 보이며, 우리의 목표는 비트가 모두 1로 채워진 값(nextNumber - 1)에 최대한 가깝게 만드는 것입니다.

• n이 1 또는 2인 경우: 이미 얻을 수 있는 최댓값이므로 제거할 요소가 없습니다.
• n == nextNumber 또는 n == nextNumber - 1: 단 하나의 요소만 제거하면 모든 비트가 1인 최댓값을 만들 수 있습니다.
• n == nextNumber - 2: 현재 XOR 값이 이미 도달 가능한 최댓값이므로 아무것도 제거하지 않아도 됩니다.
• 그 외의 경우: 짝수라면 한 번의 제거로 충분하고, 홀수라면 두 번의 제거가 필요합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

// n 이상인 2의 거듭제곱 중 가장 작은 수를 반환
int nextPowerOf2(int n){
    if (n && !(n & (n - 1))) {
        return n;
    }
    int cnt = 0;
    while (n) {
        n = n / 2;
        ++cnt;
    }
    return (1 << cnt);
}

// 제거해야 할 요소의 최소 개수를 계산
int elementsToBeRemoved(int n){
    if (n == 1 || n == 2) {
        return 0;
    }
    int nextNumber = nextPowerOf2(n);
    if (n == nextNumber || n == nextNumber - 1) {
        return 1;
    } else if (n == nextNumber - 2) {
        return 0;
    } else if (n & 1) {
        return 2;
    } else {
        return 1;
    }
}

int main(){
    int n = 10;
    cout << "Numbers to be removed = " <<
    elementsToBeRemoved(n) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Numbers to be removed = 1

N이 10일 때, 10보다 크거나 같은 2의 거듭제곱은 16입니다. 10은 16, 15, 14 어느 것에도 해당하지 않는 짝수이므로 답은 1이 됩니다. 실제로 4를 제거하면 나머지 숫자들의 XOR 값이 가능한 최댓값인 15가 됩니다.