[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