백준 2830번: 행성 X3(골드 III)

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

상근이는 초등학교 졸업 여행으로 외계 행성 X3에 방문했었다. 이 행성에 사는 사람들의 이름은 모두 자연수이다. 행성의 거주민은 모두 서로를 알고 있다. 두 X3인은 그들의 친밀도를 자신의 이름을 이진수로 바꾸어서 계산한다. 두 이름을 이진수로 바꾸고, 자리수가 짧은 쪽을 기준으로 정렬한다. 이때, 두 이진수의 각 자리 아래에 두 자리가 같으면 0을, 다르면 1을 적는다. 이 결과 이진수를 다시 10진수로 바꾸면 그들의 친밀도가 된다.

예를 들어, 10과 19의 친밀도는 25이다.

행성의 가치는 이 섬에 있는 모든 친밀도의 합이다. 행성 거주민들의 이름이 주어졌을 때, 행성의 가치를 구하는 프로그램을 작성하시오. 

첫째 줄에 X3 거주민의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 다음 N개의 줄에는 거주민의 이름이 주어진다. 이름은 1,000,000보다 작거나 같은 자연수이다. 첫째 줄에 행성 X3의 가치를 출력한다.

2020년에 처음풀고 갖다 버린(당시 고1) 문제입니다

제 프로필을 누르면 나오는 

시도했지만 맞지 못한 문제

를 없애려는중 첫타자로 걸렸죠

한 이틀? 고민한거 같네요

핵심은 O(N^2)로는 절대 시간안에 통과하지 못하므로 O(N)이나 O(NlogN) 알고리즘이 있을거라 믿었습니다

수학적 증명은 코드 밑에 있으니 심심하면 읽어보세요

#include <stdio.h>

#include <math.h>

long long sum=0;

int b[21];

int main()

{

    int N,i,n,k=1;

    scanf("%d", &N);

    for(i=0; i<N; i++)

    {

        scanf("%d", &n);

        _10to2(n);

    }

    for(i=0; i<20; i++)

        sum+=(long long)pow(2,i)*(N-b[i])*b[i];

    printf("%lld", sum);

}

void _10to2(int x)

{

    int i=0;

    while(x)

    {

        b[i]+=x%2;

        x/=2;

        i++;

    }

}

증명: n개의 수가 있고 10진수를 2진수로 변환했을때 2^0 부분이 1인 수가 x개라 치자. 

이때 친밀도의 가짓수는 n(n-1)개이다. 이대로 돌리면 100% 시간초과로 터지니 다른 방법을 고안해보자.

xor연산을 하면 서로 다를때 1이다.

1. 1일때

나머지 1의 개수 = x-1개

->얘네는 전부 0됨

따라서 1일때 1나오는 개수는 y개

2. 0일때

0일때 1나오는 개수는 x개

따라서 xy + yx = 2xy인데

이게 중복된 결과이니 /2를 해주면 xy

각 자릿수를 곱해주면 i=0에서 19까지 2^i * x * y를 다 더해주면 답