[python] 백준 25306: 연속 XOR

 

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

 

 

xor(exclusive OR) 문제이다. 처음에 문제의 조건을 자세히 읽어보지 않고, a부터b까지의 값을 모두 대입하여 계산하면 되겠다는 생각을 하였다.

#백준 25306: 연속 XOR

import sys

A, B = map(int, sys.stdin.readline().split())

result = 0

for i in range(A, B + 1):

result ^= i

print(result)

 

 

모두 대입하여 푼 결과, 결과값은 잘 출력되었지만 (문제에서 주어진 예시) 시간 초과가 발생하였다.

 

# 백준 25306: 연속 XOR

import sys

A, B = map(int, sys.stdin.readline().split())

def xor(n):

if n % 4 == 0:

return n

elif n % 4 == 1:

return 1

elif n % 4 == 2:

return n + 1

else:

return 0

 

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

 

핵심 아이디어: 

 

연속 xor을 이러한 형식으로 나타낼 수 있다는 것을 검색을 통해 확인하였다. (나름의 규칙성이 있음) XOR을 시행하기 전에 mod연산을 미리 시행하여, 나오는 값을 작은 정수의 형태로 나타낸다. 그러면 값이 너무 커져 시간초과가 나는 문제를 해결할 수 있다.