백준 / XOR 합 3 / 13710번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: XOR 합 3 / 13710번 (골드 1단계)

문제 사이트: https://www.acmicpc.net/problem/13710

 

문제 설명

---

나의 풀이

def solution(N, A):
    # prefix XOR 생성 (0 포함)
    prefix = [0]
    cur = 0
    for x in A:
        cur ^= x
        prefix.append(cur)

    answer = 0

    # 0~31비트까지 확인
    for bit in range(32):
        zero = 0
        one = 0

        for p in prefix:
            if (p >> bit) & 1:
                one += 1
            else:
                zero += 1

        answer += zero * one * (1 << bit)

    return answer


if __name__=="__main__":
    N = int(input())
    A = list(map(int, input().split()))  # 배열

    print(solution(N, A))

---

※ 알아야 할 것

문제 설명이 없어 어려울 수 있습니다!! 단계별로 설명해드리도록 하겠습니다.

예시:

N = 4
A = [1, 2, 3, 4]

 

1단계. prefix XOR 만들기

prefix[0] = 0
prefix[1] = 1
prefix[2] = 1 ^ 2 = 3
prefix[3] = 3 ^ 3 = 0
prefix[4] = 0 ^ 4 = 4

결과

prefix = [0, 1, 3, 0, 4]

 

2단계. 모든 부분배열 XOR 실제값

부분배열 [i, j] XOR = prefix[i] ^ prefix[j+1]

구간	XOR	계산
[0]	1	prefix[0] ^ prefix[1] = 0 ^ 1
[0,1]	1^2 = 3	prefix[0] ^ prefix[2] = 0 ^ 3
[0,1,2]	1^2^3 = 0	prefix[0] ^ prefix[3] = 0 ^ 0
[0,1,2,3]	1^2^3^4 = 4	prefix[0] ^ prefix[4] = 0 ^ 4
[1]	2	prefix[1] ^ prefix[2] = 1 ^ 3
[1,2]	2^3 = 1	prefix[1] ^ prefix[3] = 1 ^ 0
[1,2,3]	2^3^4 = 5	prefix[1] ^ prefix[4] = 1 ^ 4
[2]	3	prefix[2] ^ prefix[3] = 3 ^ 0
[2,3]	3^4 = 7	prefix[2] ^ prefix[4] = 3 ^ 4
[3]	4	prefix[3] ^ prefix[4] = 0 ^ 4

총합 = 1 + 3 + 0 + 4 + 2 + 1 + 5 + 3 + 7 + 4 = 30 이 됩니다.

 

3단계. 비트 단위 zero/one 카운트

prefix = [0, 1, 3, 0, 4]

2진수로 보면

값	2진수
0	0000
1	0001
3	0011
0	0000
4	0100

bit는 0~2까지만 필요

 

bit = 0 (1의 자리)

prefix 값	bit0
0	0
1	1
3	1
0	0
4	0

zero = 3
one = 2

기여도 = zero * one * (1 << 0)
= 3 * 2 * 1
= 6 이 됩니다.

 

bit = 1 (2의 자리)

prefix 값	bit1
0	0
1	0
3	1
0	0
4	0

zero = 4
one = 1

기여도 = 4 * 1 * 2 = 8 이렇게 bit 4가 될때까지 반복합니다.