[c++] 백준 #14257 XOR 방정식 (190927)

< 풀이 >

A+B = S, A^B = X를 만들 수 있는 (A, B) 쌍의 개수를 구하는 문제이다. 

문제를 풀 때 집중해야 하는 것은 xor의 성질.

xor 했을1이 되는 bit는 A나 B 둘 중 하나가 가지고 있을 것이다. 일단은 xor해서 0되는 bit는 A, B 둘 다 가지고 있지 않다고 가정하고 나머지 bit를 0으로 두자.

그러면 A^B = X가 되는 A, B의 경우의 수는 2^(켜진 비트 수) 만큼 된다. 이때 xor해서 0이 되는 경우는 모두 0으로 뒀으니 A, B는 모두 X의 각 비트를 나눠 가진 셈이니까 A + B = X이다. 그러면 이제 두 숫자 모두 켜져 있지 않은 비트를 하나씩 켜보면서 A + B = S를 만들 수 있으면(이 경우는 유일하게 하나 나온다) 가능한 모든 경우는 2^(켜진 비트 수)가 된다. 즉, X를 정의한 방식에 따라 X<=SX <=S가 성립한다. X> S이면 저런 경우를 만들 수 없다.

이때, 나의 직관으로는 놓치기 쉬운 빈틈이다. 문제의 조건에 따라 A와 B는 모두 양의 정수여야 한다. A>0, B>0 즉, 두 수 모두 최소 하나 이상의 bit를 가지고 있어야 한다는 것이다. X와 S가 동일하지 않은 경우엔 합을 S로 맞춰주는 과정에서 반드시 A>0, B>0이 보장되므로 신경 쓰지 않아도 되지만, 만약 A + B = X = S인 경우면, 2^(켜진 비트)의 경우의 수 중 A = 0, B = X 혹은 A = X, B = 0 이런 식으로 한 수에 모든 비트가 몰빵 되고 나머지 숫자는 0이 되는 경우가 존재하므로 이런 경우, (A, B) = (0, S), (S, 0)인인 2가지 경우의 수를 빼주어야 한다.

S, X 모두 다 10^12까지 숫자가 갈 수 있으므로 (10^3)^4 = 2^40까지 가야 하므로 long long 변수로 선언해준다.

// 총 시간 복잡도는 O(logN)이다. 문제의 답안을 머리로 생각해내는 것이 어려운 문제. 코딩은 쉬운 편.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll S, X;
    cin >> S >> X;
    // 10^12까지면 2^40 즉 40개의 bit만 확인하면 된다. 
    ll residue = S - X;
    int n_on_bit = 0;
    for(int bit=41; bit >= 0; bit--){
        if (X & (1LL << bit)) n_on_bit++; // XOR된 수의 켜져 있는 bit를 이용해 경우의 수를 세기 위함
        else if (residue >= (1LL << bit)*2){
            residue -= (1LL << bit) * 2;
        }
    }
    ll ans = 0;
    if (residue == 0){
        ans = (1LL << n_on_bit); 
    }
    if (S == X) ans -= 2LL; // 두 수 중 하나가 0이 되는 경우를 제외 
    cout << ans << '\n'; 
    return 0;
}

 

< 참고한 블로그 >

https://blog.naver.com/PostView.nhn?blogId=rdd573&logNo=221321759084

백준 XOR 방정식(14257번)