문제
https://www.acmicpc.net/problem/11895
문제해설
자연수 n개가 주어진다.
각각 자연수를 임의로 X나 Y그룹으로 넣어준다.
X그룹 안에 모든 수를 XOR 연산 한 것과
Y그룹 안에 모든 수를 XOR 연산 한 것이 같다면
X그룹의 합과 Y그룹의 합 중에 더 큰 수가 정답이다.
만약 어떻게 해도 X와 Y의 XOR 연산 값이 같아지지 않는다면 0을 출력한다.
문제풀이
처음에는 구현을 해야하나 고민했는데
XOR를 계속 해보다보니 문제를 파악했다.
아주 간단한 문제이다.
문제 조건중에 X그룹과 Y그룹의 XOR 값이 같아야 정답이 나오는데
XOR 연산한 값이 같다면 그 두 수의 XOR 연산값은 0이 나온다.
결국 모든 수를 XOR 했을 때 0이 나온다면
전체의 합에서 가장 작은 수를 빼주면 정답이다.
0이 아닌 값이 나온다면 0을 출력해주면 된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
int sum = 0, XOR = 0;
vector<int>arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
sum += arr[i];
XOR ^= arr[i];
}
if (XOR == 0) {
sort(arr.begin(), arr.end());
cout << sum - arr[0];
}
else
cout << 0;
return 0;
}