얼거스 개발 일지

다른사람 풀이

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public void main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] ones = new int[20];
        for (int i = 0; i < n; i++) {
            int name = Integer.parseInt(br.readLine());
            for (int j = 0; j < 20; j++) {
                if ((name & (1 << j)) > 0) ones[j]++;
            }
        }

        long sum = 0L;
        for (int i = 0; i < 20 i++) {
            sum += (1L << i) * ones[i] * (n - ones[i]);
        }
        System.out.println(sum);
    }

이 문제 공식처럼 외워서 풀어야 하는 문제인줄 알았는데 아니었다..!! 어느분이 해설 올려두신것 링크 첨부합니다 https://m.blog.naver.com/chogahui05/221258149120

아래는 식에 대한 풀이 🔻

F(a, b, c) = G(a, b, c)

F(a, b, c) = a⨁b + a⨁c + b⨁c (여기서 ⨁는 XOR 연산)
G(a, b, c) = (a b c의 0번째 자리수의 0의 개수 합 * a b c의 0번째 자리수의 1의 개수 합 * (1<<0))
			+ (a b c의 1번째 자리수의 0의 개수 합 * a b c의 1번째 자리수의 1의 개수 합 * (1<<1)) 
			+ (a b c의 2번째 자리수의 0의 개수 합 * a b c의 2번째 자리수의 1의 개수 합 * (1<<2))


a = 7, b = 3, c = 5일 때, 

a = 7 = 111 (2진수)
b = 3 = 011 (2진수)
c = 5 = 101 (2진수)

이제 F(a, b, c)를 계산해 봅시다.
F(a, b, c) = a⨁b + a⨁c + b⨁c = 7⨁3 + 7⨁5 + 3⨁5 = 4 + 2 + 6 = 12

이제 G(a, b, c)를 계산해 봅시다.

각 자리수별로 0과 1의 개수를 세어 보겠습니다.

자리수	0의 개수		1의 개수
  0			0		   3
  1			1		   2
  2			1		   2
  
G(a, b, c) = (0 * 3 * (1<<0)) + (1 * 2 * (1<<1)) + (1 * 2 * (1<<2)) 
		   = 0 + 2 * 2 + 2 * 4 
           = 0 + 4 + 8 
           = 12

따라서 F(a, b, c) = G(a, b, c) = 12 입니다.

---

처음 풀어본 날 : 23.03.25 다시 풀어본 날 : 23.03.26 _ 03.30 _ 04.01