들어가며

Candy Splitting (Large)

솔브드에서 제공하는 랜덤 마라톤에서 나온 문제입니다. XOR 연산에 대한 이해가 있어야 풀 수 있는 문제였습니다.

문제설명

형제 Sean과 Patrick은 부모님으로부터 캔디가 든 가방을 받았습니다. 가방 안에는 값이 다른 여러 개의 캔디가 들어있는데, 이를 공정한 방법으로 나누려고 합니다. Sean이 두 더미로 나누면 Patrick이 둘 중 하나를 골라 가져가는 방식이죠. 불행하게도 Patrick은 너무 어려서 캔디의 값을 올바르게 더하는 방법을 모릅니다. 대신 이진법 덧셈을 거의 할 줄 아는데, 올림을 까먹었습니다. 예를 들어, 12(1100), 5(101)이 있을 때 올바른 덧셈 결과는 17(10001)이지만, Patrick의 방식으로는 9(1001)가 됩니다.

이때, Sean이 캔디를 어떻게 나누면, Patrick의 방식으로 같은 값이라고 착각하면서 가장 많은 값의 캔디를 가져갈 수 있을까요?

해설

Patrick의 덧셈 방식은 XOR 연산입니다.

•

Patrick은 이진수 덧셈에서 carry(올림)을 무시합니다. → XOR 연산

Sean이 두 개의 그룹으로 나누었을 때, 각 그룹의 XOR 연산 결과가 동일해야 Patrick이 행복합니다.

•

A = 11, B = 11 → Patrick 행복 / A = 11, B = 12 → Patrick 불행

따라서, 두 개의 그룹을 XOR 연산했을 때, 결과가 0이 되어야 Patrick이 행복할 수 있습니다. 그렇지 않다면 어떤 식으로 나누어도 두 그룹이 같지 않습니다.

왜 XOR 연산 결과가 0이면 나눌 수 있을까?

XOR 연산의 성질에 대해 알아야 합니다.

XOR연산은 교환 법칙과 결합 법칙을 만족합니다.

(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

a ⊕ b = b ⊕ a

같은 숫자를 XOR하면 0이 됩니다.

a ⊕ a = 0

예) 5 ⊕ 5 = 0, 1001 ⊕ 1001 = 0000

0과 XOR하면 원래 값을 유지합니다.

a ⊕ 0 = a

따라서 Sean이 캔디를 두 그룹으로 나누는 순간 각 그룹의 XOR 값이 같아야 합니다.

•

두 그룹 A, B가 있을 때 A ⊕ B = 0를 만족

•

전체 XOR 값이 S일 때, S = a1 ⊕ a2 ⊕ a3 ⊕ a4 ⊕ a5 ⊕ a6 ⊕ aN

코드

결국 모든 캔디의 XOR연산의 값이 0일 때, 두 그룹으로 나눌 수 있고, Patrick에게 가장 작은 값의 캔디만 주면 됩니다.

(Sean의 캔디) ⊕ (Patrick의 캔디) = 0이 되기 때문이죠.

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

public class Main {
    static int T;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i < T + 1; i++) {
            int N = Integer.parseInt(br.readLine());
            int[] candies = new int[N];
            int xor = 0;
            int total = 0;
            int minValue = Integer.MAX_VALUE;

            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                candies[j] = Integer.parseInt(st.nextToken());
                xor ^= candies[j];
                total += candies[j];
                minValue = Math.min(minValue, candies[j]);
            }

            if (xor == 0) {
                sb.append("Case #").append(i).append(": ").append(total - minValue).append("\n");
            } else {
                sb.append("Case #").append(i).append(": ").append("NO").append("\n");
            }
        }

        System.out.println(sb);
    }
}

Loading comments...