문제 개요
이 문제에서는 두 개의 양의 정수 n과 k가 주어집니다. 우리가 해야 할 일은 1부터 n까지의 숫자들 중 k개를 사용하여 만들 수 있는 최대 XOR 값을 찾는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력 − n = 5, k = 2
출력 − 7
설명 −
5까지의 숫자는 1, 2, 3, 4, 5입니다.
가능한 모든 XOR 쌍:
1^2 = 3, 1^3 = 2, 1^4 = 5, 1^5 = 4
2^3 = 4, 2^4 = 6, 2^5 = 7
3^4 = 7, 3^5 = 6
4^5 = 1
따라서 최댓값은 7입니다.
접근 방법
이 문제를 해결하기 위한 핵심 아이디어는 다음과 같습니다. 어떤 숫자 조합으로 얻을 수 있는 최대 XOR 값은 숫자의 모든 비트가 1로 설정된 경우에 나타납니다.
예를 들어, 숫자가 5라면 이진수로 101이고, 따라서 가능한 최대 XOR 값은 모든 비트가 1인 111, 즉 10진수로 7이 됩니다.
다만 예외적인 경우가 있습니다. 최대 XOR을 위해 사용할 숫자의 개수가 1개라면, 최대 XOR 값은 단순히 n 자체가 됩니다. 그 외의 경우(k ≥ 2)에는 비트를 모두 1로 채운 값이 곧 최대 XOR 값입니다.
구체적으로, n보다 크거나 같아질 때까지 1을 왼쪽 시프트한 뒤 1을 빼면, n의 비트 길이와 같거나 바로 다음 길이의 모든 비트가 1인 값을 얻을 수 있습니다.
예제 코드
아래 프로그램은 위 해결 방법의 동작을 보여줍니다.
#include <iostream>
using namespace std;
int maxXor(int n, int k) {
if (k == 1)
return n;
int result = 1;
while (result <= n)
result <<= 1;
return result - 1;
}
int main() {
int n = 5, k = 2;
cout<<"1부터 "<<n<<"까지의 숫자 중 "<<k<<"개를 사용한 최대 XOR 값은 "<<maxXor(n, k);
return 0;
}
출력 결과
1부터 5까지의 숫자 중 2개를 사용한 최대 XOR 값은 7
정리
이 알고리즘의 시간 복잡도는 O(log n)으로 매우 효율적입니다. k가 1인 경우에는 답이 n이 되고, k가 2 이상인 경우에는 n의 비트 표현을 기준으로 모든 비트가 1인 가장 작은 값을 계산하면 됩니다. 이 방식은 실제로 두 수를 조합했을 때 해당 값이 항상 만들어질 수 있음을 보장합니다.