[JAVA][백준 16713] Generic Queries

https://www.acmicpc.net/problem/16713

 

 

 

---

풀이

해당 문제는 누적합을 이용해서 푸는 문제이다.

주어진 구간 사이의 모든 원소를 XOR하는 문제인데 입력값 범위가 매우 넓어 값이 주어질 때마다 계산을 하면 시간초과가 발생한다. 

따라서 처음부터 n까지 누적XOR연산을 한 값을 기록하고 0부터 ei까지 XOR값과 0부터 si-1까지 XOR한 값을 XOR하면 된다.

 

문제를 처음 보고 XOR연산에 대해 잘 모르고 있어서 누적합인지 뭔지도 몰랐다.

그래서 XOR에 대해서 알아봤는데

 

XOR은 비트 연산 중 하나로 값이 같으면 0, 값이 다르면 1을 출력한다.

XOR연산의 주요 성질을 살펴보면 사칙연산과 비슷하다.

1. 자기 자신과 XOR하면 0이된다

2. 0과 XOR하면 자기자신이 된다.

3. 순서가 바뀌어도 결과는 같다. (교환법칙 성립)

4. 그룹으로 묶을 수 있다. (결합법칙 성립)

5. 어떤 수를 두 번 XOR하면 원래 값으로 돌아온다.

위의 성질을 알고 문제를 접근하면 매우 쉬운 문제이나, 해당 내용을 모르면 풀기 어려운 문제인 것 같다.

 

코드 순서를 살펴보면

1. 입력값을 배열에 저장한다.

2. 누적 XOR을 연산하여 배열에 저장한다.

3. 누적XOR 배열을 이용하여 0부터 ei까지의 누적XOR값과 0부터 si까지의 누적XOR값을 XOR 연산한다.

 

 

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


public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());    // 수열의 길이
        int Q = Integer.parseInt(st.nextToken());    // 쿼리의 개수

        st = new StringTokenizer(br.readLine());
        int[] num = new int[N + 1];
        int[] xor = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
            xor[i] = xor[i - 1] ^ num[i];
        }

        int answer = 0;
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            answer ^= xor[s - 1] ^ xor[e];
        }

        System.out.println(answer);


    }
}