[BOJ][Math][실1][20153] 영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해!

문제 링크

문제 링크

첫 번째 풀이

알고리즘

쉽게 정리한 XOR에서 xor의 특징을 정리해두었습니다.

우선 아래 문장 의미를 제대로 이해해야합니다.

그 후 각 정수 x에 대해 2x가 홀수 개 존재하면 2x를 더하고, 짝수 개 존재하면 더하지 않는다. 이렇게 했을 때 얻을 수 있는 최대 합을 2번 출력하라.

모든 N개의 자연수를 영웅이의 표현법으로 바꾼 뒤, 전체에 대해서 항의 갯수가 홀수개인 2^x만 더해서 출력하라는 말입니다.

그런데 짝수 개면 더하지 않는다는 부분에서, XOR의 특징이 사용됩니다. a^a^b처럼 같은 값을 짝수번 XOR하게 되면 0이 됩니다. 그리고 0이랑 XOR을 하면 값이 변하지 않습니다.

예제 입력 1에 대해서 자연수 전체를 xor해둔 x를 저장합니다.

x = 5 ^ 7 ^ 11

그리고 최대 한 개의 자연수를 제거해야하니 아래의 경우 중 최대값을 찾습니다.

x     // 0개의 자연수를 제거한 경우
x ^ 5 // 1개의 자연수를 제거한 경우
x ^ 7 // 1개의 자연수를 제거한 경우
x ^ 11 // 1개의 자연수를 제거한 경우

XOR을 사용한 결과의 최대값을 찾았기 때문에 위 4개의 XOR 결과들은 모두 2^x 항을 1개씩만 가지고 있습니다. 만약 짝수개였다면 XOR의 특징에 의해서 사라질테니까요

x       // 5 ^ 7 ^ 11
x ^ 5   //     7 ^ 11
x ^ 7   // 5     ^ 11
x ^ 11  // 5 ^ 7

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX = 2'222'225;
int v[MAX];
int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  int x = 0;
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    x ^= v[i];
  }
  int ans = x;
  //cout << bitset<8>(ans) << "\n";
  for (int i = 0; i < n; i++) {
    ans = max(ans, x ^ v[i]);
    //cout << bitset<8>(ans) << "\n";
  }
  cout << ans << ans << "\n";
  return 0;
}

Success Notice: XOR 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.