BOJ 29441

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

 

 

코드

http://boj.kr/5a53c2b9a48c4aa1b32320178de76059

 

Russian Olympiad in Informatics 2011-2012 Season A

 

난이도 : P3

 

Elapse Time : 15min

 

처음에는 여러개를 xor할 수 있는줄 알고 가우스 소거를 할 생각을 했다. 그러나 하나만 xor하는 것이었고 다른 풀이를 생각하기 시작했다. xor연산이기도 하고 가장 큰 값을 만드는 것이 목적이므로 큰 비트부터 그리디하게 처리하면 되겠다는 생각을 했다. 이를 시간 안에 처리하기 위해 정렬을 해놓고 범위를 줄여나가는 것이 가능하겠다는 생각이 들었다. 30번째 비트부터 보면서 현재 비트가 몇인 것이 유리한지, 그것이 가능한지를 판단하고 범위를 줄여나가는 방법으로 답을 구했다.