[백준] 2830번 - 행성 X3

💎 문제 링크

2830번: 행성 X3

 

📝 문제

 

✍🏻 입력 & 출력

 

🤔 풀기 전에 생각하기

문제는 두 사람 끼리의 친밀도를 모두 구해 더하는 것이다.

사람이 몇 명 이든 두사람끼리 짝지어서 친밀도를 모두 구해야 하는 문제이기 때문에 경우의 수를 생각해야 한다.

2진법은 자리수 마다 0 또는 1로 구성되어 있고 (1, 1), (0, 0)은 어차피 0이기 때문에 경우의 수에 포함되지 않는다.

 

(1, 0) 과 같이 두자리가 각자 다른 수 일 때 경우의 수가 1 증가하는 것이기 때문에

(1의 개수 x 0의 개수) x 자릿수 를 해야한다.

 

자릿수는 2^0, 2^1, 2^2, 2^3, ... 을 곱해야 하기 때문에 '<<' 연산으로 증가시킬 수 있다.

 

✨ 풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt(); // 행성의 인구 수 입력
        int[] cases = new int[N]; // 사람 수 만큼 친밀도 입력 받을 배열
        long answer = 0L;

        for (int i = 0; i < N; i++) {
            cases[i] = scanner.nextInt(); // 사람마다 친밀도 입력
        }

        int[] oneCnt = new int[20];
        /*
         * 2진법의 각 자리마다 1의 개수를 세서 넣은 배열 생성
         *
         * 배열의 크기를 20으로 잡는 이유는
         * 사람의 수는 최대 1,000,000 명 인데 2^10 이 1,024 인 것에서
         * 1,024 * 1,024 는 대략 1,000,000에 가깝기 때문에
         * 2^10 * 2^10 = 2^20 이기 때문에 배열의 크기를 20으로 잡는다.
         */
        for (int i = 0; i < N; i++) {
            /*
             * 각 자리마다 1이 발견되면 oneCnt[i]++;
             */
            int j = 0;
            while (cases[i] != 0) {
                oneCnt[j] += cases[i] % 2;
                cases[i] /= 2;
                j++;
            }
        }

        for (int i = 0; i < oneCnt.length; i++) {
            answer += (1L << i) * oneCnt[i] * (N - oneCnt[i]);
            /*
             * 문제는 모든 사람들과의 친밀도를 다 더하는것.
             * 예를 들어 2진수의 1의 자리를 두 사람씩 짝지을 때
             * 두 수가 1, 0 으로 다른 수여야만 1이 증가한다.
             * 그렇기 때문에 두사람의 각각 1의 자리 숫자가 (1, 1) 일때나 (0, 0) 일 때는 어차피 0이기 때문에 생각하지 않아도 된다.
             * 1과 0이 따로 따로 나올 경우만 생각해주고 자리수만큼 곱해줘야 하기 때문에
             * (1L << i)은 2진수의 자릿수를 왼쪽으로 이동하므로써 1, 2, 4, 8, ... 을 나타내고
             * oneCnt[i]는 그 자리에 1이 있을 경우
             * N - oneCnt[i]는 그 자리에 0이 있을 경우
             * 두 경우를 곱해서 1과 0이 다르게 나올 경우의 수를 구하는 것이다.
             */
        }

        System.out.println(answer);
    }
}