[Coding/Backjoon] 2830번 행성 X3

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

2830번: 행성 X3

 

 

 

 

 

---

 

 

 

 

 

1. 문제 풀이 방법

---

이 문제를 이해하기까지 너무 어려웠다. 이 문제에서 원하는 것은 3명 이상의 이름이 주어지면 각각 2명씩 모두 비교하여 나온 친밀도를 다 합하는 것이 정답이였다.

XOR 연산을 하기 때문에 (각 자리의 1의 갯수) * (각 자리의 0의 갯수) * 2^i 를 하여 나온 모든 값들의 합이 정답이다. 각 자리에 존재하는 1의 갯수를 one 배열에 저장한다. 예를 들어 2^1 자리에 1이 2개가 존재하므로 one[1] =2 가 되는 것이다.

 

 

 

 

 

 

---

 

 

 

 

 

2. 코드 구현 부분

---

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();     // 거주민의 수 N
        int[] one = new int[20];
        
        for (int i = 0; i<n ; i++) {
        	int data = sc.nextInt();
            int idx = 0;
            while (data > 0) {
            	int tmp = data % 2;
                data = data / 2;
                if (tmp == 1) {
                	one[idx] += 1;
                }
                idx += 1;
            }
        }
        
        long result = 0L    // int 의 최댓값을 넘어가기 때문에 int로 하게 되면 값이 제대로 나오지 않는다.
        for(int i = 0; i<one.length; i++) {
        	result = result + (1L << i) * one[i] * (n-one[i]);
        }
        
        System.out.print(result);
    }
}

 

• result 값이 int 의 최대값을 넘어서기 때문에 long형으로 선언한다.
• long형으로 선언할 때에는 L 을 같이 써야한다.
• (1L << i) 는 2^0 , 2^1, 2^2,... 을 의미한다.
• one[i] 는 1의 갯수, n-one[i] 는 0의 갯수를 의미한다