N개의 원소를 가진 배열 A와 또 다른 값 K가 주어졌다고 가정해 봅시다. 0부터 K 범위 안의 정수 X에 대해 f(X) = (X xor A[1]) + (X xor A[2]) + ... + (X xor A[N])으로 정의할 때, f가 가질 수 있는 최댓값을 구하는 것이 우리의 목표입니다.
예를 들어 입력이 K = 7, A = [1, 6, 3]이라면 출력은 14가 됩니다. 그 이유는 f(4) = (4 XOR 1) + (4 XOR 6) + (4 XOR 3) = 5 + 2 + 7 = 14이기 때문입니다.
해결 접근 방식
이 문제는 각 비트(bit)를 독립적으로 고려하는 그리디(greedy) 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 상위 비트부터 하위 비트까지 순서대로 검사합니다.
- 각 비트 위치에서 배열 원소들 중 해당 비트가 1로 설정된 개수를 셉니다.
- X의 해당 비트를 1로 설정해도 K를 초과하지 않는다면, 비트를 설정했을 때와 설정하지 않았을 때 어느 쪽이 더 큰 합을 만드는지 비교하여 더 유리한 쪽을 선택합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
n := 배열 A의 크기
45부터 0까지 i를 감소시키며 반복:
p := 2^i
m := 0
j를 0부터 n-1까지 증가시키며 반복:
만약 A[j] AND p가 0이 아니라면:
m을 1 증가
만약 o + p <= k라면:
만약 m < n - m이라면:
m := n - m
o := o + p
d := d + p * m
d 반환C++ 코드 구현
아래 코드를 통해 실제 구현 방법을 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
long solve(int k, vector<int> A){
long n = A.size(), d = 0, m, p, o = 0;
for (long i = 45; i >= 0; i--){
p = pow(2, i);
m = 0;
for (int j = 0; j < n; j++){
if (A[j] & p)
m++;
}
if (o + p <= k){
if (m < n - m){
m = n - m;
o += p;
}
}
d += p * m;
}
return d;
}
int main(){
int K = 7;
vector<int> A = { 1, 6, 3 };
cout << solve(K, A) << endl;
}동작 원리 설명
코드의 주요 변수들은 다음과 같은 역할을 합니다.
- d: 최종 결과값으로, 각 비트별 기여도를 누적합니다.
- o: 지금까지 X의 비트를 선택하면서 만든 임시 값으로, K를 초과하지 않도록 관리합니다.
- m: 현재 비트 위치에서 1인 비트를 가진 원소의 개수입니다.
각 비트 위치에서 o + p ≤ k 조건을 만족하면 X의 해당 비트를 1로 설정할 수 있습니다. 이때 m < n - m이라면, 즉 비트를 설정함으로써 XOR 연산 후 1이 되는 원소가 더 많아진다면 m을 n - m으로 갱신하고 o에 p를 더합니다. 마지막으로 d에 p × m을 누적하여 모든 비트의 기여도를 합산합니다.
실행 결과
입력:
7, { 1, 6, 3 }출력:
14
이 알고리즘은 비트 수에 비례하여 동작하므로 시간 복잡도는 O(46 × N)으로 매우 효율적입니다. 배열의 크기가 커져도 빠르게 답을 계산할 수 있다는 장점이 있습니다.