[BOJ/JAVA] 2830. 행성 X3

---

문제 설명

문제 링크

---

접근 방법

처음에 문제를 읽어봤을 때 바로 XOR 연산임을 눈치채고 호기롭게 거주민의 수는 유심히 안보고 모든 합을 구해서 풀었다. 그렇게 하면 시간복잡도가 $O(N^2)$이 되므로 시간 초과가 나온다. 고민해보다 도저히 생각이 안 나서 검색을 좀 해보고, 전부 구할 필요는 없다는 힌트를 보고 조금 더 생각해보다가 발견했다.

XOR 연산은 서로 다를때 결과가 1이므로, 모든 수들의 비트를 각각 세어서 1인 비트 수와 0인 비트 수를 곱해주면 그것이 해당 비트의 총 경우의 수가 될 것이다.

예시 2 ) 7 3 5
7 = 111 3 = 011 5 = 101
가장 왼쪽 비트의 값은 1 0 1 (1 2개, 0 1개) 을 가지고 있다.
여기서 XOR 연산이 1이 되는 경우는 (1 0), (0 1) 이 가능하다.
즉 1의 개수와 0의 개수를 곱해주면 가능한 총 개수가 되며, 
자리수에 해당하는 값(4)를 곱해주면 해당 비트의 총합이 된다.

이 방법으로 모든 수를 이진수로 변환하여 (중학생 쯤에 배운 십진수 -> 이진수 변환에서 아이디어를 얻었다.) 비트의 수를 전부 구해준 다음, 경우의 수를 계산하여 각각의 값에 이진수의 자리수를 곱해주면 되겠다. 범위는 1000000 까지이므로 비트의 수는 20개만 준비하면 된다.

여기서 한번 더 생각 안했던 게 있다. 최대 $2^{19}$의 자릿수에서 갯수를 계산하면 int 로는 담아낼 수가 없을 수 있다. 그래서 총합(행성의 가치)은 꼭 long 에 담아야 한다.

소스 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] bitCount = new int[20];
        int index = 0;
        long sum = 0L;
        for (int i=0; i<n; i++) arr[i] = Integer.parseInt(br.readLine());

        for (int i=0; i<n; i++) {
            int a = arr[i];
            index = 0;
            while (a > 0) {
                bitCount[index++] += a%2;
                a /= 2;
            }
        }

        for (int i=19; i>=0; i--) {
            sum += (long) bitCount[i]*(n-bitCount[i]);
            sum <<= 1;
        }
        sum >>= 1;

        bw.write(sum +"\n");
        bw.flush();
        br.close();
        bw.close();
    }
}

제출 결과

---

마무리하며

골드 3 문제면 지금까지 풀어봤던 문제들 중 가장 수준이 높은 문제다. 그러면서 비트 연산자를 활용하는 것도 이번 문제가 처음인데 역시 생각하는게 쉽지 않아서 인터넷을 찾아보고 나서야 그 아이디어를 기반으로 해결할 수 있었다. 이런 문제도 바로 생각해서 풀어낼 수 있기...에는 갈 길이 아직 먼 것 같다. 차근차근 다지면서 올라갈 수 있도록 해야겠다.