[BOJ] 20153 영웅이는 2의 거듭 제곱을 좋아해! - C++

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

20153번: 영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해!

문제 해석

1. 영웅이는 어떤 자연수 $A_n$을 2의 거듭제곱의 합으로 표현한다고 했는데 2진수로 나타내는 것과 같다.
2. $A_n$ 중 최대 한 개의 자연수를 제외할 수 있다. 즉, 하나도 제외하지 않아도 된다.
3. $2^x$가 홀수개면 $2^x$를 결과에 더한다. 즉, 2진수로 표현했을 때 1이 홀수개 존재하는 자리는 1, 짝수개라면 0이 되고 이 값의 최댓값을 찾아야 한다.

아이디어

$A_n$을 각각 2진수로 고친 후 1이 홀수개인 자리를 구해 최댓값을 찾아도 AC를 맞을 수 있다. 하지만, 구현이 많고 속도도 그렇게 빠르지 않다. 그래서 떠올린 기법은 XOR이었다. XOR은 연산하는 두 비트가 다르면 1, 같으면 0을 반환하는데 $N$번의 연산에서는 1이 홀수개면 1, 짝수개면 0의 값을 가지게 된다. 또, $2^x$를 하나하나 계산해 더할 필요 없이 $A$ ^ $B$가 계산이 모두 완료된 값이 된다.

다만, $N$개의 자연수를 배열에 담고 하나씩 제외해가면서 XOR연산을 수행한 결과 시간초과를 받았다. 그래서 생각한 방법으로 같은 숫자로 XOR을 2번 하면 다시 원래의 숫자로 돌아온다는 것이다. 수식으로 표현하면 아래와 같다.

$$ A \text{^} B \text{^} B = A $$

전체적인 알고리즘을 서술해보면 아래와 같다.

 

1. 각 숫자를 입력받으며 XOR연산을 수행한다. 모든 숫자에 대해 XOR을 수행한 결과가 아무 숫자도 제외하지 않았을 때의 결과값이다.
2. XOR의 결과를 복원할 수 있다는 점을 이용해 하나의 숫자를 제거해보고 최댓값을 비교한다.

코드

#include <iostream>

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    int a[n];
    int target = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        target ^= a[i];
    }

    int ans = target;

    for (int i = 0; i < n; i++) {
        int temp = target ^ a[i];
        if (temp > ans) {
            ans = temp;
        }
    }

     cout << ans << ans;
}

 

참고

$0 \text{^} A = A$ 가 성립한다.