[BOJ / Python] 16713 : Generic Queries

 

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

 

문제 코드 - 첫번째

 

import sys

input = sys.stdin.readline

n, q = map(int, input().split())

li = list(map(int, input().split()))

prefix_sum = [0] * (n+1)

query = []

for i in range(1, n+1):
    prefix_sum[i] += li[i-1] ^ prefix_sum[i-1]

for j in range(q):
    s, e = map(int, input().split())
    if(s == 1):
        query.append(prefix_sum[e])
    else:
        query.append(prefix_sum[e] ^ prefix_sum[s-1])

ans = 0

for idx in query:
    ans = ans ^ idx

print(ans)

 

 

문제 풀이

 

XOR 연산의 성질에 대해 잘 알고 있으면 어렵지 않게 풀 수 있는 문제이다. (난 XOR 연산이 어떤건진 알고 있었는데 성질에 대해서는 잘 몰랐어서 시간이 조금 걸렸던 것 같다.)

 

우선 수열 N을 입력 받아서 수열에 대한 누적 XOR을 배열에 저장을 해주고 Q개의 쿼리를 입력 받아서 쿼리의 답을 전부 XOR 연산 해주면 된다. 

 

문제에서 쿼리의 답은 구간 [s, e] 에 대한 XOR 연산값 인데 코드에 보면 prefix_sum[e] ^ prefix_sum[s-1] 이라고 적혀있다.

 

이렇게 적을 수 있는 이유는 우선 prefix_sum[e]를 풀어서 쓰면 a1 ^ a2 ^ … ^ a_{s-1} ^ a_s ^ … ^ a_e 이고, prefix_sum[s-1]은 a1 ^ a2 ^ … ^ a_{s-1} 이다. 여기서 XOR 연산은 교환/결합 법칙이 성립하고, 자기 자신과 XOR 연산을 하면 0으로 지워지기 때문에 prefix_sum[e] ^ prefix_sum[s-1] = (a_s ^ … ^ a_e) 이라고 할 수 있는 것이다. 

 

이렇게 쿼리의 답을 구하고 이 결과들을 다 XOR 연산해주면 답이 나온다. 

 

근데 처음에 짠 코드를 다시 보니까 불필요한 부분이 많은거 같아서 코드를 다시 짜보았다.

 

 

문제 코드 - 두번째

 

import sys

input = sys.stdin.readline

n, q = map(int, input().split())

li = list(map(int, input().split()))

prefix_sum = [0] * (n+1)

for i in range(1, n+1):
    prefix_sum[i] += li[i-1] ^ prefix_sum[i-1]

ans = 0

for j in range(q):
    s, e = map(int, input().split())
    ans ^= prefix_sum[e] ^ prefix_sum[s-1]

print(ans)

 

우선 쿼리의 답을 구할 때 if s == 1같은 분기 처리를 할 필요가 없었다. (prefix_sum[0] = 0이고, 0과 XOR 연산을 해도 값은 그대로이기 때문에 prefix_sum[e] ^ prefix_sum[s-1]로 다 처리가 가능하다.)

 

그리고 처음에는 쿼리의 답을 저장할 배열을 만들어서 저장한 후에 답을 계산했는데 그럴 필요 없이 그냥 바로 계산해도 결과가 나온다.