[백준] 21099 - Four XOR (c++)

https://www.acmicpc.net/problem/21099

 

문제 요약

N개의 서로 다른 수가 주어진다. 숫자 4개를 뽑아 xor 했을때 0이 되는 경우의 수가 있는지 구해라.

 

풀이 (X^2)

• 비둘기집 원리

4개를 2개씩 묶는다고 생각해보면 0이 되는 경우의 수는 어떻게 묶던 둘이 같아진다(xor값이). 그럼 2개 묶었을 때 같은 수가 2개 이상 있으면 참이 되는데 2개 묶었을 때 최대값이 대충 10^6이라 쳐도 제한이 크게 줄어들어 모든 경우를 확인하며 풀 수 있게 된다.

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    int a[n];
    for(int& x:a)cin>>x;

    if(n>1000) {
        cout<<"Yes";
        return 0;
    }
    bool ans=0;
    set<int> s;
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            int x=a[i]^a[j];
            if(s.count(x))
                ans=1;
            s.insert(x);
        }
    }
    cout<<(ans?"Yes":"No");
}

 

 

좀 짧게 짜면 이렇게도 짤 수 있다.

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    int a[n],c[200000]{};
    for(int& x:a)cin>>x;

    for(int i=0;i<n;i++) 
        for(int j=i+1;j<n;j++) 
            if(++c[a[i]^a[j]]==2) return cout<<"Yes",0;
    cout<<"No";
}