문제 설명

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

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

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

분석

처음에 설명을 잘 알아먹지 못했는데 예시를 보니 XOR 연산임을 알 수 있었다.

행성의 친밀도 = 모든 주민의 1대1 친밀도의 합

그럼 모든 주민의 조합을 더해야 할까?

조합처럼 보이는 문제가 사실은 조합 문제가 아니었던 적이 많았기에 조금 더 생각해봤다.

xor 연산은 각 비트(자리)끼리 연산하는 비트연산이다.
따라서 전체 연산을 각 비트에 대한 연산으로 쪼개고 합해도 된다. 물론 자리에 따른 계수(?)를 곱해줘야 한다.

어떠한 자리에서, 1의 수 0의 수 = 연산 결과가 1인 경우의 수이다.
따라서 임의의 자리 i에 대해 1의 수 0의 수를 해주면 각 자리 연산 결과가 1인 경우의 수 Ki를 알아낼 수 있다.
그 다음, 모든 i에 대해 Ki에 2를 자릿수만큼 곱해주어 더하면 완성.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] ones = new int[20]; // name은 2진수로 최대 20자리
        for (int i = 0; i < n; i++) {
            int name = Integer.parseInt(br.readLine());
            for(int j = 0; j < 20; j++) {
                if((name & (1 << j)) > 0) ones[j]++;
            }
        }

        long sum = 0L;
        for (int i = 0; i < 20; i++) {
            // 0의 개수 * 1의 개수 * 2^자리수
            sum += (1L << i) * ones[i] * (n - ones[i]);
        }
        System.out.println(sum);
    }
}