문제 개요
정수 S와 K가 주어졌을 때, 두 양수의 합이 S가 되고 비트 단위 XOR 연산 결과가 K가 되는 순서쌍(ordered pair)의 개수를 구하는 것이 목표입니다.
해결 방법은 간단합니다. i를 1부터 S-1까지, j를 i+1부터 S까지 증가시키며 가능한 모든 쌍을 탐색하고, 어떤 쌍 (i, j)가 i + j == S와 i ^ j == K 조건을 동시에 만족하면 카운트를 2씩 늘립니다. (i, j)와 (j, i)는 원소의 순서가 다르므로 서로 다른 순서쌍으로 각각 세어 주기 위함입니다.
입출력 예제
입력
S = 10, K = 4
출력
합이 S이고 XOR이 K인 순서쌍의 개수: 2
설명: 조건을 만족하는 쌍은 (3, 7)과 (7, 3)입니다.
입력
S = 12, K = 6
출력
합이 S이고 XOR이 K인 순서쌍의 개수: 0
설명: 조건을 만족하는 순서쌍이 존재하지 않습니다.
풀이 접근 방법
- 정수 S와 K를 입력으로 받습니다.
- sumXOR(int s, int k) 함수는 합이 s이고 XOR이 k인 순서쌍의 개수를 계산하여 반환합니다.
- 순서쌍을 세기 위한 변수 count를 0으로 초기화합니다.
- 중첩된 두 개의 반복문으로 가능한 모든 쌍을 만들어 봅니다.
- i는 1부터 s-1까지, j는 i+1부터 s까지 증가시킵니다.
- 각 쌍 (i, j)에 대해 (i + j == s) && (i ^ j == k) 조건을 검사하고, 참이면 count를 2 증가시킵니다. (i, j)와 (j, i)는 서로 다른 순서쌍이기 때문입니다.
- 모든 반복이 끝나면 count에 조건을 만족하는 순서쌍의 총 개수가 저장됩니다.
- count 값을 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int sumXOR(int s, int k){
int count = 0;
for (int i = 1; i < s; i++){
for(int j = i + 1; j < s; j++){
// 합 조건과 XOR 조건을 동시에 만족하는지 확인
if((i + j) == s && (i ^ j) == k){
count += 2; // (i,j)와 (j,i)는 서로 다른 두 순서쌍
}
}
}
return count;
}
int main(){
int S = 9, K = 5;
cout << "합이 S이고 XOR이 K인 순서쌍의 개수: " << sumXOR(S, K);
return 0;
}
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
합이 S이고 XOR이 K인 순서쌍의 개수: 4
S = 9, K = 5일 때 조건을 만족하는 쌍은 (2, 7), (7, 2), (3, 6), (6, 3)으로 총 4개입니다.
시간 복잡도 최적화
위 풀이는 두 수를 모두 탐색하므로 시간 복잡도가 O(S²)입니다. 그러나 j는 항상 s - i로 유일하게 결정되기 때문에 반복문 하나만으로도 충분하며, 이렇게 하면 시간 복잡도를 O(S)로 줄일 수 있습니다.
int sumXOR(int s, int k){
int count = 0;
for (int i = 1; 2 * i < s; i++){ // i < j가 자동으로 보장됨
int j = s - i;
if((i ^ j) == k){
count += 2; // (i,j)와 (j,i)는 서로 다른 두 순서쌍
}
}
return count;
}
참고로 a + b = (a XOR b) + 2 × (a AND b)라는 성질이 성립하므로, 해가 존재하려면 S ≥ K이고 (S - K)가 짝수여야 합니다. 탐색 전에 이 조건을 먼저 확인하면 불필요한 연산을 더욱 줄일 수 있습니다.