[백준][JAVA] 2830번: 행성x3 - 3%에서 실패 해결...

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

2830번: 행성 X3

원리만 알면 나름 간단해지는 문제였다!

 

정말 두 개씩 확인하면서 모든 경우의 수를 합해주면 시간 초과가 뜬다!

아래처럼..!

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr= new int[n];
        for(int i = 0 ; i<n ; i++){
            arr[i] = scan.nextInt();
        }
        int count = 0;
        for(int i=0; i <arr.length -1 ;i++){
            for(int j=i+1 ; j<arr.length ; j++){
                count+=((arr[i]|arr[j]) & ~(arr[i]&arr[j])); // ^ 연산자가 있는데 생각이 안났다.
            }
        }
        System.out.print(count);
    }
}

위의 코드는 처음에 푼 방식.. 적으면서도 시간초과 뜰 것 같았는데 역시나다.

 

그래서 다시 생각해낸 방식이 아래의 방식이다.

 

한꺼번에 할 수 있는 방법이 없을까.. 고민하다

각 자리의 수에서 1과0을 뽑을 경우의 수만 알면 되는 것이었다.

왜냐하면 서로 달라야 즉 1과 0이어야 1이 되니까 말이다!

 

그리하여 같은 자리에서 1의 개수와 0의 개수를 곱해주면 

두개씩 엮어서 친밀도를 구했을 때의 해당자리의 1의 개수를 알아낼 수 있다..(말이 어렵다..)

 

다만 2진수 인점을 고려하여 2의 0승 2의 1승 ... 곱해주는 것을 잊지말자.

혹시, 이해가 안되는 분들을 위해 조금 더 설명하자면

각 자리의 수는 다른 자리의 수에 영향을 끼치지 않습니다.

각 자리 수만 2개씩 비교를 해서 답을 내니까요

그래서 각자리수의 1몇개와 0몇개에서 1과0 두개(순서x) 뽑을 경우의 수를 구한다고 생각해주시면 됩니다.

1이 올 확률 = 1의 개수
0이 올 확률 = 0의 개수

각 자리수는 1과 0밖에 없으므로
1의 개수 + 0의 개수 = 전체의 개수
즉 1의 개수는 = 전체의 개수 - 0의 개수
     0의 개수는 = 전체의 개수 - 1의 개수

다시 말해서 각자리수의 1몇개와 0몇개에서 1과0을 뽑을 경우의 수를 구하려면
1의 개수 * 0의 개수 입니다.
= 1의 개수 * (전체개수 - 0의 개수)

그리고 마지막으로 각 자리수는 이진수를 나타내고 있으니
각 자리수에 맞는 2^n 을 곱해주어 다 더하면 값이 나옵니다!

대충 다른 예를 들자면 파란색 공 3개와 빨간색공 2개에서
빨간색공하나와 파란색공 하나를 뽑을 확률은
3*2 인것입니다!

추가로 왜 1하나 0하나 경우의 수를 구해주냐면
두개가 다를때가 1이 되주는데
두개가 다를때는 1과 0밖에 없기 때문입니다!

즉 1과 0이 올때만 1이 되는데
해당 1의 개수를 세어주는게 목표기 때문에 1과 0이 올 때의 경우의 수만 생각하면 됩니다!

아래는 참고 그림

사실 이 방법을 알고나서도 안되서 한참을 걸렸다..

계속 반례가 뭘지...

내가 로직을 잘 못 짠건가... 해서 계속 쳐다봤는데 알고보니 

위의 코드가 되기전에 count1의 변수가 int타입이었다.

 

해당 count1을 이용하여 answer을 계산해주었기 때문에 int로 자동 형변환이 되어 잘못된 값이 나왔던 것이다 ㅠㅠㅠ

 

3%에서 계속 막히시는 분들은 int타입의 범위를 생각해주세요 ㅠㅠ

 

코드는 아래와 같습니다.

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr= new int[n];
        int max = 0;
       
        for(int i = 0 ; i<n ; i++){
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(arr[i], max);
        }
        long ss = 1;
        long answer = 0;
        while(max != 0){
            long count1 = 0;
            for(int i=0; i <arr.length ;i++){
                if(arr[i] == 0)continue;
                if(arr[i]%2 == 1) count1++;
                arr[i] /= 2;
            }    
            answer += ((count1 * (n - count1)) * ss);
            // answer += (((long)count1 * (n - count1)) * (long)ss);
            ss = ss << 1;
            max/=2;
        }
        
        System.out.print(answer);
    }
}