백준) 25306 - 연속 XOR [파이썬 3]

문제) 준원이는 다음과 같이 A 에서 B 까지의 자연수들을 나열했다.

이 수들에 모두 비트 XOR을 취한 값을 구하라.

 

입력) 두 자연수 A, B가 공백을 사이에 두고 주어진다.

 

출력) A 이상 B 이하인 모든 자연수들을 XOR한 값을 구하여라.

A, B = map(int, input().split())

def xor(n):
    start = n//4 * 4
    answer = 0
    for i in range(start, n+1):
        answer ^= i
    return answer

print(xor(A-1) ^ xor(B))

풀이 : 코딩을 하기 전 문제에 핵심이 되는 규칙부터 살펴보자.

 문제에서 원하는 [A, B]의 연속 XOR 값은 [1, A - 1]의 연속 XOR 값과 [1, B]의 연속 XOR 값의 XOR과 같다.

[A, B] == [1, A - 1] xor [1, B]

 그럼 1부터 n까지의 xor값을 구하면 문제를 해결할 수 있을 텐데 단순히 1부터 계산한다면 오히려 시간을 더 잡아먹는 방법이 될 것이다. 그렇기에 위의 표와 같은 규칙을 찾아야하는 데 표를 보면 n을 4로 나누었을 때 나머지가 3일 때마다 [1, n]이 0이라는 것을 알 수 있다. 위의 규칙을 그대로 코드로 옮기면 문제를 해결할 수 있다.