2830번: 행성 X3

• 첫째 줄에 거주민의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
• 다음 N개의 줄에는 거주민의 이름이 주어진다. 이름은 1,000,000보다 작거나 같은 자연수이다.
• 거주민의 이름끼리 XOR 연산을 한 결과 값을 친밀도라고 한다.
• 친밀도의 총 합을 구하여라.

접근

N의 범위

N이 최대 1,000,000 이기 때문에 시간복잡도가 O(N)이어야한다.

XOR 연산의 시간 복잡도

거주민들 끼리 모두 XOR 연산을 한다면 시간복잡도가 O(N!)일 수밖에 없다.
따라서 이 문제는 설명하는 대로 정직하게 구현을 했다가는 '시간초과'만을 볼 것이다.

XOR 연산의 특징

그렇다면 어떻게 이 문제를 해결해야할까?
답은 XOR 연산의 특징에 있다.
XOR 연산은 서로 다른 비트의 경우에만 1을, 아닐경우 0이 된다.
그리고 각 자리의 비트는 다른 자리의 비트에 영향을 미치지 않는다.
만약에 여러 숫자들끼리 서로 XOR 연산을 한다고 해보자.

111 = 7
011 = 3
101 = 5

세 개의 숫자가 있다고 생각했을 때, 7^3, 7^5, 3^5의 연산을 풀어헤쳐보자.

(7의 2번비트 ^ 3의 2번 비트) X (2의 2제곱) + (7의 1번비트 ^ 3의 1번 비트) X (2의 1제곱) + (7의 0번비트 ^ 3의 0번 비트) X (2의 0제곱) = 7 ^ 3

(7의 2번비트 ^ 5의 2번 비트) X (2의 2제곱) + (7의 1번비트 ^ 5의 1번 비트) X (2의 1제곱) + (7의 0번비트 ^ 5의 0번 비트) X (2의 0제곱) = 7 ^ 5

(3의 2번비트 ^ 5의 2번 비트) X (2의 2제곱) + (3의 1번비트 ^ 5의 1번 비트) X (2의 1제곱) + (3의 0번비트 ^ 5의 0번 비트) X (2의 0제곱) = 3 ^ 5

패턴이 보이는가? (2의 m제곱)으로 연산을 모두 묶을 수 있다는 것이 보일 것이다.
결국 구해야하는 값은 각 숫자의 비트를 XOR 연산한 결과들의 합 X 비트 자리 수에 따른 2의 m제곱이 된다.
여기까지 오면 결국엔 각각의 숫자들을 XOR 연산하는건 같다고 생각할 수 있다.
하지만 XOR 연산의 특징을 통해 이 연산을 간단하게 만들 수 있다.

XOR 연산은 같은 1과 1끼리, 그리고 0과 0 끼리의 결과는 0이 된다.
다시 7, 3, 5의 2번째 비트를 보자.

7^3은 1과 0이므로 1
7^5는 1과 1이므로 0
3^5는 0과 1이므로 1

1이 결과가 되는 경우는 서로다른 1과 0이 등장하는 빈도수가 된다는 것을 볼 수 있다.
따라서 XOR 연산으로 1이 나오는 경우의 수는 해당 비트 자리의 1비트의 수 X 0비트의 수가 된다.

만약 각 숫자들의 비트수가
1 1 1 1 1 1 1 1 1 1 이라면 0이 나올 수밖에 없다. 1^1=0 이므로
1 1 1 1 1 1 1 1 1 0 이라면 각 1 비트가 0과 만날때마다 1이 되므로 9*1이 된다.
따라서 XOR 연산의 결과는 1과 0이 서로 만나는 경우의 수가 되는 것이다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		input(in);
		solve();
	}
	
	static int cnt;
	static long[] bit;
	static void input(BufferedReader in) throws IOException {
		cnt = Integer.parseInt(in.readLine());
		bit = new long[20];
		
		for(int i = 0; i < cnt; i++) {
			int citizen = Integer.parseInt(in.readLine());
			for(int j = 0; j < 20; j++) {
				if((citizen & (1 << j)) == (1 << j)) bit[j]++;
			}
		}
	}
	
	static void solve() {
		long sum = 0;
		
		for(int i = 0; i < 20; i++) {
        	// 1비트의 수 * 0비트의 수 * 2의 i 제곱
			sum += bit[i] * (cnt - bit[i]) * (long)Math.pow(2, i); // 형변환 필수
		}
		
		System.out.println(sum);
	}
}

회고

Math.pow의 반환값이 Double이기에 소수점 값이 곱했을 때 문제가 될 수 있다. 따라서 형변환을 함으로써 소수점 자리를 제거해주어야한다.
물론, 2의 제곱수이기 때문에 Math.pow를 사용하지 않고 비트연산인 (1 << i)을 사용하는 것이 더 나을 것이다.