[BOJ] 2830: 행성 X3 Solution

문제 소개

 

2020.03.02 기준,  골드 4티어 문제입니다.

 

처음에 이 문제를 접했을 때는 XOR 비트 연산과 관련이 있겠구나만 생각하면서 어렵다고 생각했습니다. 근데 한번 생각을 비틀고나니 골드 4티어?라는 티어가 이해가 안 갈 정도로 쉬워진 문제입니다.

 

문제 링크

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

2830번: 행성 X3

아이디어

어떤 사람 A와 B의 이름(자연수)이 주어졌을 때, 이 둘의 친밀도는 XOR 연산을 한 결과입니다.

 

아, 그럼 모든 사람의 친밀도를 일일이 구하면 되지 않을까하고 접근할 수 있지만, N의 범위가 1<= N <=1,000,000 이기 때문에 O(n^2) 알고리즘은 택도 없습니다.

 

그러면 한번 생각해봅시다.

 

만약에 사람마다 뒤에서부터 i번째 비트에 있는 1의 개수와 0의 개수를 안다면, 1의 개수와 0의 개수를 곱하고 2**i를 곱하면 i번째 비트로 하여금 발생하는 친밀도의 합을 구할 수 있습니다. 그러면, 사람의 이름(자연수)을 이진수로 바꾸고 비트마다 개수를 누적하면 된다는 결론이 나옵니다.

 

1,000,000는 최대 20비트 안에 표현할 수 있고, 백만 x 20 번안에 모든 연산을 할 수 있다는 것입니다.

아래는 이 아이디어를 반영한 코드입니다.

코드

import sys
n = int(sys.stdin.readline())
L = [int(sys.stdin.readline()) for i in range(n)]

D = [0]*30

for i in L:
    k = i
    cnt = 0
    while k > 0:
        D[cnt] += k%2
        k//=2
        cnt+=1
ans = 0
c = 1
for i in D:
    ans += c*(i*(n-i))
    c*=2
print(ans)

 

 

 

Rmx