백준 2830번 - 행성 X3

나의 풀이.

비트연산자로 가볍게 풀 수 있다고 생각했던 내가... 또르르..
먼저 각 A, B, C 라는 사람이 있으면 A와 B, A와 C, B와 C의 친밀도를 더해야 하는 문제다.
일단 여기서부터 문제 잘못해석해서 한 번 좌절..
두번째로 거주민의 수 N의 범위에 좌절... 

        int intimacy = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i+1; j <arr.length ; j++) {
                intimacy += (arr[i] ^ arr[j]);
            }
        }
        System.out.println(intimacy);

처음 작성했던 코드
예제는 다 맞았지만 제출 후에는 어림없지! 시간초과!
시간 복잡도와 비트 연산자와 어떻게 해결해야 할지 고민고민하다
검색 ㄱㄱ.. 

package day013;

import java.util.*;

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

        int N = sc.nextInt();
        int[] countOneArray = new int[20];

        int inputNumber;
        int tmp = 0;
        int index;
        long answer = 0L;

        for (int i = 0; i < N; i++) { // N번째 까지 돌면서
            inputNumber = sc.nextInt(); // input 받은 숫자를
            index = 0;
            while (inputNumber != 0) {
                tmp = inputNumber % 2; // 2로 나눈 나머지가
                inputNumber = inputNumber / 2; // 19 -> 9 -> 4 -> 2 -> 0이면 반복문 종료
                if (tmp == 1) { // 1이면
                    countOneArray[index]++; // 해당 index에 1의 개수 증가
                }
                index++; // index 증가
            }
        }

        for (int i = 0; i < 20; i++){
            answer += (1L << i) * countOneArray[i] * (N - countOneArray[i]);
            // answer += (1L << i) ->  2의 i승 * 1의 갯수 * 0의 갯수
            System.out.printf("%d += (%d << %d) * %d * (%d - %d) ==> \n",answer, 1L, i,countOneArray[i], N, countOneArray[i]);
        }

        System.out.println(answer);

    }
}

도저히 이해 안되서 계산식 출력해서 하나씩 뜯어보니 절반정도 이해가 되었다..
비트 연산자 익숙치 않은것도 있지만 무엇보다 풀이 방식이 생각안난게 좌절이다
그래도 공부해야지ㅣㅣㅣㅣㅣㅣㅣ
이번 문제는 꼭 다시 풀어봐야겠ㄷ ㅏ.

 

---

문제출처 : https://www.acmicpc.net/problem/2830