[BOJ] 10464번 XOR

링크: https://www.acmicpc.net/problem/10464

---

문제

S에서 F까지의 모든 정수를 XOR한 값은 무엇일까?

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다.

다음 T 개의 줄에는 두 개의 정수 S와 F가 주어진다. (1 ≤ S ≤ F ≤ 1,000,000,000)

출력

각 테스트 케이스마다 S에서 F까지의 모든 정수를 XOR한 값을 출력한다.

시간 제한

1초

---

첫번째 시도

T = int(input())

_ = [list(map(int, input().split())) for i in range(T)]

for S, F in _:
    num = S
    for i in range(S+1, F+1):
        num ^= i
    print(num)

문제를 처음 접했을 때는 단순히 변수 하나를 두고 S부터 F까지 XOR 연산을 수행하는 코드를 작성했다.

당연히 최악의 경우에는 1부터 10억까지 연산해야 하니 시간 초과가 날 것 같았다. (실제로 로컬에서 돌려보니 오래 걸렸음)

두번째 시도

이후 패턴을 찾아보기로 하고, S부터 F까지 xor 연산 결과값을 출력하였다.

그랬더니 S와 F의 홀수 짝수 여부에 따라 케이스가 나뉘는걸 확인했다.

1. S 짝수

S = 2
F = 20

num = S
for i in range(S+1, F+1):
    num ^= i
    print(num)

1
5
0
6
1
9
0
10
1
13
0
14
1
17
0
18
1
21

결과를 보면 0과 1로 반복되는걸 확인할 수 있다.

 

1) F가 짝수인 경우.

F-S를 2로 나눈 몫이 홀수인 경우, 결과로 1^F를 출력하게 된다.

F-S를 2로 나눈 몫이 짝수인 경우, 결과로 0^F를 출력하게 된다.

 

2) F가 홀수인 경우.

F-S를 2로 나눈 몫이 홀수인 경우, 결과로 0를 출력하게 된다.

F-S를 2로 나눈 몫이 짝수인 경우, 결과로 1를 출력하게 된다.

2. S 홀수

S = 3
F = 20

num = S
for i in range(S+1, F+1):
    num ^= i
    print(num)

7
2
4
3
11
2
8
3
15
2
12
3
19
2
16
3
23

결과를 보면 S와 S-1로 반복되는걸 확인할 수 있다.

 

1) F가 짝수인 경우.

F-S를 2로 나눈 몫이 홀수인 경우, 결과로 (S-1)^F를 출력하게 된다.

F-S를 2로 나눈 몫이 짝수인 경우, 결과로 S^F를 출력하게 된다.

 

2) F가 홀수인 경우.

F-S를 2로 나눈 몫이 홀수인 경우, 결과로 (S-1)을 출력하게 된다.

F-S를 2로 나눈 몫이 짝수인 경우, 결과로 S를 출력하게 된다.

 

위 결과를 바탕으로 다음과 같은 코드를 작성하였다.

def range_xor(S, F):
    diff = (F - S) // 2 % 2

    if S % 2 == 0 and F % 2 == 0: # S 짝수, F 짝수
        if diff == 0: return 0^F
        else: return 1^F
    elif S % 2 == 0 and F % 2 == 1: # S 짝수, F 홀수
        if diff == 0: return 1
        else: return 0
    elif S % 2 == 1 and F % 2 == 0: # S 홀수, F 짝수
        if diff == 0: return S^F
        else: return (S - 1)^F
    elif S % 2 == 1 and F % 2 == 1: # S 홀수, F 홀수
        if diff == 0: return S
        else: return S - 1

T = int(input())

_ = [list(map(int, input().split())) for i in range(T)]

for S, F in _:
    print(range_xor(S, F))

이 코드로 제출하니 AC를 받았다!

---

여담

다른 사람들의 코드를 보니, 1부터 F까지의 XOR에서 패턴을 찾더라.
이건 4로 나눈 나머지에서 깔끔하게 패턴이 나오기 때문에, 누적합 느낌으로 풀면 위의 복잡한 함수 조건식 없이 더 쉽게 할 수 있었겠다는 생각이 들었다.

 

feat. https://www.geeksforgeeks.org/dsa/calculate-xor-1-n/