[BOJ/백준][Gold3] 2830 : 행성 X3 (C++)

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

2830번: 행성 X3

 

 

[난이도] Gold3
[유형] 비트마스킹

[풀이]
모든 주민의 이름을 서로 XOR 계산을 하게 되면 O(N^2)의 시간복잡도로 시간초과가 발생하게 됩니다.

잘 생각해보면 각 XOR 계산의 결과가 얼마인지는 알 필요가 없고 총 합만 구하면 되기 때문에,
각 자리수끼리의 XOR 연산에서 총 얼마의 친밀도가 발생하는지 계산해서 답에 더해주면 됩니다.
예를 들어,

1001
0110
1000

위와 같이 세가지 수가 있을 때, 제일 좌측 4번째 자릿수의 값은 각각
1
0
1

입니다. 여기서 1이 2개, 0이 1개이기 때문에 서로간의 XOR 연산에서
2x1=2 가 생김을 알 수 있습니다.
이 숫자에 자릿수 2^3을 곱해주면 2 x (2^3) 이 되는데 이 값을 답에 더해주면 4번째 자릿수에서
발생하는 숫자의 계산은 끝이 납니다.

이렇게 모든 자릿수에 대해서 위와 같이 1과 0이 몇개 있는지를 체크해서 답에 더해주면 됩니다.

 

#include <cstdio>
int N;
long long onecnt[20];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        int j=0;
        while(1){
            if(v/2==0) {
                onecnt[j]++;
                break;
            }
            onecnt[j++]+=v%2;
            v/=2;
        }
    }
    long long ans=0;
    for(int i=0;i<20;i++) ans+=(1<<i)*(N-onecnt[i])*onecnt[i];
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2830.cpp