본문 바로가기

알고리즘 관련/BOJ

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한 결과가 같을 것이다.


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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}
 
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1733 등번호  (2) 2017.01.03
BOJ)14168 Cow Checklist  (0) 2017.01.03
BOJ)2401 최대 문자열 붙여넣기  (1) 2016.12.30
BOJ)13168 내일로 여행  (0) 2016.12.30
BOJ)13911 집 구하기  (0) 2016.12.30