C++에서 배열의 비트 OR 최댓값 구하기 – 원소에 x를 k번 곱하기

문제 설명

N개의 정수로 이루어진 배열이 주어집니다. 배열의 모든 원소에 대한 비트 OR(bitwise OR) 값을 최대화해야 하며, 사용할 수 있는 작업은 단 하나뿐입니다.

허용된 작업: 배열에서 임의의 원소 하나를 골라, 주어진 정수 x를 최대 k번 곱하는 것입니다.

예를 들어 입력 배열이 {4, 3, 6, 1}이고 k = 2, x = 3이라면, 얻을 수 있는 최댓값은 55입니다.

접근 방법

핵심 아이디어는 간단합니다. 어떤 원소에 x를 k번 곱하는 것은 x^k(x의 k제곱)를 한 번 곱하는 것과 같으므로, 미리 x^k를 계산해 두면 됩니다. 그다음 각 원소를 차례로 '곱셈 대상'으로 가정하면서, 나머지 원소들의 OR 값과 합쳐 보고 그중 최댓값을 찾으면 됩니다.

1. 각 원소에 대해, 해당 원소에 x^k를 곱한 값과 왼쪽(앞쪽) 원소들의 비트 OR를 연산합니다.
2. 여기에 오른쪽(뒤쪽) 원소들의 비트 OR까지 함께 연산합니다.
3. 모든 원소에 대한 시도가 끝나면 그중 최댓값을 반환합니다.

왼쪽 원소들의 OR은 접두사(prefix) 배열에, 오른쪽 원소들의 OR은 접미사(suffix) 배열에 미리 누적해 두면 매번 처음부터 다시 계산할 필요가 없습니다. 덕분에 전체 시간 복잡도를 O(n + k)로 유지할 수 있습니다.

C++ 예제 코드

#include <bits/stdc++.h>
using namespace std;

int getMaxOr(int *arr, int n, int k, int x){
    int prefixOr[n + 1];  // 왼쪽 원소들의 OR 누적값
    int suffixOr[n + 1];  // 오른쪽 원소들의 OR 누적값
    int power = 1;
    for (int i = 0; i < k; ++i) {
        power = power * x;  // power = x^k
    }
    prefixOr[0] = 0;
    for (int i = 0; i < n; ++i) {
        prefixOr[i + 1] = prefixOr[i] | arr[i];
    }
    suffixOr[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        suffixOr[i] = suffixOr[i + 1] | arr[i];
    }
    int result = INT_MIN;
    for (int i = 0; i < n; ++i) {
        result = max(result, prefixOr[i] | (arr[i] * power) | suffixOr[i + 1]);
    }
    return result;
}

int main(){
    int arr[] = {4, 3, 6, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    int x = 3;
    cout << "Result = " << getMaxOr(arr, n, k, x) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

Result = 55

동작 과정 살펴보기

k = 2, x = 3이므로 power = 9입니다. 네 원소를 차례로 곱셈 대상으로 삼아 계산해 보면 다음과 같습니다.

• 4 × 9 = 36 → 36 | 3 = 39
• 3 × 9 = 27 → 4 | 27 | 7 = 31
• 6 × 9 = 54 → 7 | 54 | 1 = 55
• 1 × 9 = 9 → 7 | 9 = 15

따라서 최댓값은 55이며, 이는 세 번째 원소 6에 9를 곱했을 때 얻어지는 값입니다. 이처럼 접두사·접미사 OR 배열을 활용하면 각 원소를 한 번씩만 확인해도 정답을 효율적으로 구할 수 있습니다.