16713번 Generic Queries

문제 설명

주어진 수열에서 XOR 연산을 하는 query를 여러 개 수행한 결과값들을 다시 XOR연산을 한 값을 구하는 문제입니다.

 

 

문제 풀이

선행 지식

XOR

• Python에서 XOR 연산은  "^"를 통해 이루어진다.
• XOR 연산의 결과 값
  • 0 ^ 0 = 0
  • 0 ^ 1 = 1
  • 1 ^ 0 = 1
  • 1 ^ 1 = 0
• a1^a2^a3^a4 = A라고 할 경우 A^a1 = a2^a3^a4이다.

 

풀이

개념

이번 문제는 XOR의 개념을 생각하는 데에 오래 걸린 것 같습니다..

수열의 길이 N과 쿼리의 개수가 모두 10^6로 큰 수 입니다.

그러므로 한 쿼리마다 XOR 연산을 하는 것은 비효율적이므로 누적합을 통해 이용해보도록 하겠습니다.

 

여기서 헷깔렸던 점은 수열의 홀수번째부터 시작하는 누적합과 짝수번째부터 시작하는 누적합이 다를 것이라고 생각한 것입니다.

하지만, 위의 XOR 선행 지식의 3번째 문항을 생각해보면 홀수번째부터 시작하든, 짝수번째부터 시작하든 누적합은 변함이 없다는 것을 확인할 수 있습니다.

 

풀이 순서

1. 주어진 a수열의 누적 XOR을 구해줍니다. (입력된 query는 1부터 시작하므로 편의를 위해 누적합의 첫 번째 인덱스에 임의로 0을 넣어줍니다.)
2. s e 형식의 쿼리문을 진행합니다. (누적XOR[e] - 누적XOR[s-1]을 해줘야 s~e의 누적XOR이 구해집니다. 1~e에서 1~s-1을 빼줘야 s~e의 누적 XOR이 구해지므로)
3. 진행한 쿼리문의 결과값을 차례대로 XOR 연산해줍니다.

 

 

해결

논리연산자를 이용한 문제를 오랜만에 해서 개념이 헷깔렸지만, 이 기회에 생각하면서 얻어낸 것들을 잊지 말아야할 것 같습니다. (예. XOR 선행지식 3번째 문항)

 

문제 링크 : https://www.acmicpc.net/problem/16713

16713번: Generic Queries

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/1304.py