문제 개요
배열이 주어졌을 때, 두 원소를 골라 비트 OR(Bitwise OR) 연산을 수행한 결과가 홀수가 되는 쌍(pair)의 개수를 구하는 문제입니다.
예시
입력
arr = [1, 2]
출력
1
배열 [1, 2]에서 만들 수 있는 쌍은 (1, 2) 하나뿐이며, 1 | 2 = 3으로 홀수이므로 정답은 1입니다.
핵심 아이디어
비트 OR 연산의 결과는 두 수 중 하나라도 홀수(마지막 비트가 1)이면 항상 홀수가 됩니다. 반대로 두 수가 모두 짝수일 때만 결과가 짝수가 되죠. 이 성질을 이용하면 단순한 완전 탐색뿐 아니라 O(n) 시간 복잡도의 최적화된 풀이도 가능합니다.
알고리즘 (브루트 포스)
- 배열을 임의의 숫자로 초기화합니다.
- 쌍의 개수를 저장할 변수 count를 0으로 초기화합니다.
- 두 개의 중첩 반복문으로 배열의 모든 쌍(i, j)을 탐색합니다.
- 각 쌍에 대해 비트 OR 연산을 수행합니다.
- 결과가 홀수이면 count를 1 증가시킵니다.
- count 값을 반환합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int getOddPairsCount(int arr[], int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((arr[i] | arr[j]) % 2 != 0) {
count++;
}
}
}
return count;
}
int main() {
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = 10;
cout << getOddPairsCount(arr, n) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
35
배열 {1, 2, ..., 10}에서 만들 수 있는 전체 쌍은 C(10, 2) = 45개이며, 이 중 두 수가 모두 짝수인 쌍은 C(5, 2) = 10개입니다. 따라서 45 − 10 = 35개의 쌍이 홀수가 됩니다.
최적화된 접근 방법
위 성질을 활용하면 모든 쌍을 직접 확인하지 않고도 답을 구할 수 있습니다.
- 전체 쌍의 개수 = n × (n − 1) / 2
- 두 수가 모두 짝수인 쌍의 개수 = e × (e − 1) / 2 (e는 배열 내 짝수의 개수)
- 정답 = 전체 쌍의 개수 − 모두 짝수인 쌍의 개수
#include <bits/stdc++.h>
using namespace std;
int getOddPairsCountOptimized(int arr[], int n) {
int evenCount = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 0) evenCount++;
}
int totalPairs = n * (n - 1) / 2;
int evenPairs = evenCount * (evenCount - 1) / 2;
return totalPairs - evenPairs;
}
int main() {
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = 10;
cout << getOddPairsCountOptimized(arr, n) << endl;
return 0;
}
브루트 포스 방식은 O(n²)의 시간 복잡도를 가지지만, 최적화된 방법은 배열을 한 번만 순회하면 되므로 O(n)으로 해결할 수 있습니다. 입력 크기가 클수록 최적화된 접근 방식이 훨씬 효율적입니다.