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