[BOJ 30406] 산타 춘배의 선물 나눠주기

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 1G

Problem type
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

산타 춘배</p>

산타 춘배는 아기 고양이들에게 나눠줄 선물을 정리하고 있다. 총 $N$개의 선물을 $\frac{N}{2}$마리의 아기 고양이들에게 2개씩 나누어 주려고 한다. 여기서 $N$은 짝수이다.

$N$개의 상품은 각각 가격이 있고, 이 가격은 $0$ 이상 $3$ 이하의 정수이다. 한 아기 고양이가 선물을 받을 때 얻는 만족도는, 받은 선물 2개의 가격을 XOR한 값이다. 예를 들어 선물 2개의 가격이 각각 $1$, $2$라면 만족도는 $1$ XOR $2 = 3$이고, 선물 2개의 가격이 각각 $3$, $3$이라면 만족도는 $3$ XOR $3 = 0$이다.

산타 춘배는 아기 고양이들에게 어떻게 선물을 나눠주어야 만족도 총합이 최대가 될지 고민 중이다. 춘배를 위해 이를 계산하는 프로그램을 만들어 주자!

입력 형식

첫 번째 줄에 춘배가 가지고 있는 선물의 개수 $N$이 주어진다. $(2 \le N \le 200\,000,\ N$은 짝수$)$</p>

두 번째 줄에 선물 $N$개의 가격이 공백으로 구분되어 주어진다. 상품의 가격은 모두 $0$ 이상 $3$ 이하의 정수이다.

출력 형식

산타 춘배가 아기 고양이들에게 선물을 나눠줬을 때 얻을 수 있는 만족도의 최댓값을 출력하라.

예제 입력 1

6
0 1 2 3 2 3

예제 출력 1

7

예제 입력 2

2
3 3

예제 출력 2

0

힌트

XOR의 정의는 여기에서 확인할 수 있다.


Comments

There are no comments at the moment.