BOJ)11895 속이기

문제: icpc.me/11895

XOR의 원리에 의해서 답이되는 X그룹과 Y그룹이 존재한다면 X그룹과 Y그룹을 각각 XOR한 결과는 같으므로 결국 모든 원소들을 XOR을 한 결과는 0이 되어야 한다.

따라서 전체를 XOR했을 때 0이 아닌 다른 수가 나온다면 X그룹과 Y그룹이 존재할 수 없으므로 0을 출력하면 되고

X그룹과 Y그룹이 존재하는 경우에는 전체를 XOR한 경우가 0이므로 A^0 = A에 의하여 그룹을 어떻게 나누더라도 XOR한 결과가 같을 것이다.

문제에서는 최댓값을 출력하라고 하였으므로 파셜섬 한 값에서 가장 작은 값을 빼준 값을 출력해주면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n, x, Psum;
int arr[1010];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        x ^= arr[i];
        Psum += arr[i];
    }
    sort(arr, arr + n);
    if (x)
        printf("0\n");
    else
        printf("%d\n", Psum - arr[0]);
    return 0;
}