(a XOR x) + (b XOR x)의 최솟값을 구하는 C++ 프로그램

두 개의 숫자 a와 b가 주어졌을 때, 임의의 값 x에 대해 (a XOR x) + (b XOR x)가 가장 작아지도록 만드는 최솟값을 구해야 합니다.

예를 들어 입력이 a = 6, b = 12라면 출력은 10이 됩니다. x = 4일 때 (6 XOR 4) + (12 XOR 4) = 2 + 8 = 10이기 때문입니다.

접근 방법

이 문제의 핵심은 각 비트 자리를 독립적으로 분석하는 것입니다.

• a와 b의 해당 비트가 같은 경우: x의 그 비트를 같은 값으로 설정하면 두 XOR 결과가 모두 0이 되어 합에 아무것도 더해지지 않습니다.
• a와 b의 해당 비트가 다른 경우: x의 비트를 무엇으로 설정하더라도 두 XOR 결과 중 정확히 하나는 1이 됩니다. 따라서 그 비트 자리의 가중치(2^i)만큼은 반드시 더해집니다.

결국 최종 최솟값은 a와 b에서 서로 다른 비트만 남은 값, 즉 a XOR b 그 자체가 됩니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다 −

return a XOR b

예제

다음 구현을 통해 더 잘 이해해 보겠습니다 −

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

int solve(int a, int b){
   return (a^b);
}
int main(){
   int a = 6;
   int b = 12;
   cout << solve(a, b) << endl;
}

입력

6, 12

출력

10

복잡도 분석

시간 복잡도: O(1) — 단 한 번의 XOR 연산만 수행합니다.
공간 복잡도: O(1) — 추가적인 메모리를 사용하지 않습니다.