SWEA 10762. 사탕 나누기

사탕이 담긴 각각의  사탕 봉지들을 두명이서 나누어 사탕을 최대한 공평하게 나눌 때, 같은 기준이 XOR 합일 때 한쪽이 가질 수 있는 실제  합의 최댓값을 구하는 문제이다. 같을 수 없는 경우, NO를 출력한다.

 

나누었을 때 XOR합이 같은 경우는 모든 사탕 봉지 안에 들어있는 사탕의 수를 XOR 했을 때 0이어야 한다. 즉 XOR 합이 0이 아니면 같을 수 없으며, 한쪽이 가질 수 있는 실제 합의 최댓값은 모든 사탕의 수 - 가장 장은 사탕 봉지의 사탕 수 이다.

long totalSum = 0;
int xorSum = 0;
int minCandy = Integer.MAX_VALUE;
            
for (int i = 0; i < n; i++) {
    int candy = Integer.parseInt(st.nextToken());
                
    totalSum += candy;
    xorSum ^= candy;
    minCandy = Math.min(minCandy, candy);
}
            
if (xorSum != 0) sb.append("NO\n");
else sb.append(totalSum - minCandy).append("\n");

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            long totalSum = 0;
            int xorSum = 0;
            int minCandy = Integer.MAX_VALUE;
            
            for (int i = 0; i < n; i++) {
                int candy = Integer.parseInt(st.nextToken());
                
                totalSum += candy;
                xorSum ^= candy;
                minCandy = Math.min(minCandy, candy);
            }
            
            if (xorSum != 0) sb.append("NO\n");
            else sb.append(totalSum - minCandy).append("\n");
        }
        
        br.close();
        System.out.print(sb);
    }
}