문제 개요
양의 정수로 이루어진 두 개의 배열이 주어졌을 때, 각 배열에서 크기가 같은 부분 배열(sub-array)을 하나씩 선택하고, 두 부분 배열의 모든 원소에 비트 OR 연산을 적용해 그 합을 계산합니다. 목표는 이 OR 합이 최대가 되도록 부분 배열을 선택하는 것입니다.
예시
다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
arr1[] = {1, 2, 4, 3, 2}
arr2[] = {1, 3, 3, 12, 2}이 경우 아래와 같이 두 부분 배열을 만들었을 때 최댓값을 얻을 수 있습니다.
Subarr1[] = {2, 4, 3}
Subarr2[] = {3, 3, 12}Subarr1의 OR 값은 7, Subarr2의 OR 값은 15이므로 최종 결과는 7 + 15 = 22가 됩니다.
알고리즘
이 문제의 핵심은 비트 OR 연산의 단조성(monotonicity)입니다. OR 연산은 이미 켜져 있는 비트를 절대 0으로 되돌리지 않기 때문에, 원소를 추가로 포함할수록 결과값은 같아지거나 커질 뿐 작아지지 않습니다.
따라서 각 배열에서 가능한 한 많은 원소를 포함하는 것이 유리하며, 결국 배열 전체를 하나의 부분 배열로 선택하면 각 배열의 OR 값이 최대가 됩니다. 이를 수식으로 표현하면 다음과 같습니다.
f(arr1, 1, n) + f(arr2, 1, n)
여기서 f(a, l, r)은 배열 a의 l번째부터 r번째 원소까지의 OR 값을 의미합니다.
정리하면 알고리즘은 다음과 같습니다.
- 첫 번째 배열의 모든 원소를 순회하며 OR 값을 누적합니다.
- 두 번째 배열의 모든 원소를 순회하며 OR 값을 누적합니다.
- 두 OR 값을 더한 결과를 반환합니다.
시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int getMaximumSum(int *arr1, int *arr2, int n) {
int sum1 = 0;
int sum2 = 0;
for (int i = 0; i < n; ++i) {
sum1 = sum1 | arr1[i];
sum2 = sum2 | arr2[i];
}
return sum1 + sum2;
}
int main() {
int arr1[] = {1, 2, 4, 3, 2};
int arr2[] = {1, 3, 3, 12, 2};
int n = sizeof(arr1) / sizeof(arr1[0]);
cout << "Maximum result = " << getMaximumSum(arr1, arr2, n) << endl;
return 0;
}실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.
Maximum result = 22
마무리
부분 배열의 크기를 자유롭게 선택할 수 있다는 조건 때문에 복잡해 보이지만, OR 연산의 단조성 덕분에 배열 전체를 선택하는 것이 항상 최적이라는 점이 이 문제의 핵심입니다. 비트 연산 문제를 풀 때는 각 연산이 지닌 성질(단조성, 교환법칙, 결합법칙 등)을 먼저 파악하면 훨씬 간단하고 효율적인 해법을 찾을 수 있습니다.