[백준] BOJ 30961 : 최솟값, 최댓값

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

30961번: 최솟값, 최댓값

문제의 조건을 읽어보면 아래와 같습니다.

 

1. 수열의 힘은 해당 수열의 최댓값 * 최솟값입니다.

2. 길이가 1 이상인 모든 부분 수열의 수열의 힘들을 XOR한 결과를 출력해야 합니다.

3. 여기서 부분 수열이란 수열의 순서를 유지하면서 1 ~ N개의 원소를 골라서 만들 수 있는 수열을 의미합니다. 굳이 연속적일 필요가 없습니다.

 

사실 문제의 지문에서 그냥 조건들만 적혀져 있기 때문에, 굳이 요약을 안하더라도 쉽게 파악할 수 있습니다.

 

우선, 저는 이 문제를 보고 관찰 문제라고 생각했습니다. 왜냐하면 N의 범위가 매우 커서 O(NlogN)이나 O(N) 정도만 가능했기 때문이죠. 또한, 문제가 모든 부분 수열의 XOR한 결과를 출력하라길래 조합론 및 수학 문제일 것이라는 판단을 하였습니다. (실제로도 그렇습니다.) 그러면 각 원소가 최댓값인 경우의 수가 몇 개나 나올 수 있는지, 최솟값인 경우의 수가 몇 개가 나올 수 있는지 파악해보기로 했습니다.

 

이를 위해서는 일단 정렬을 하는게 최선이라고 판단했고, 손으로 계산해보니 K번째로 큰 원소가 최댓값인 경우의 수는 2^K가지의 경우의 수라는 것을 파악하였습니다. 그 중에서 L번째로 큰 원소가 L < K라는 경우에는 2^(K-L-1)가지의 경우의 수가 생깁니다. 여기서 저는 힌트를 얻었습니다. XOR의 특성으로는 같은 값을 짝수번 XOR를 하면 원래의 값으로 돌아가는 성질이 있습니다. 원래의 값으로 돌아간다면 굳이 XOR 결과에 반영이 안 되니 무시해도 되겠죠? 그리고 경우의 수를 보면 2의 몇 승으로 표현이 됩니다. 즉 경우의 수가 2^0이 아니라면 굳이 반영을 할 필요가 없고 이를 만족하는 L은 K-1밖에 없습니다.

 

그래서 일단 정렬을 하고 인접한 두 수의 곱들을 모두 XOR, 그리고 당연히 길이가 1인 부분 수열도 한 번씩만 나오므로 자기 자신을 제곱한 수들을 모두 XOR하여 출력하도록 코드를 짰더니 정답이 나왔습니다. 코드는 아래와 같고 총 시간복잡도는 정렬하는데 O(NlogN), 결과 구하는 데 O(N)이라서 O(NlogN)이 나왔습니다.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    ll N;
    cin >> N;
    
    vector<ll> A(N);
    ll ans = 0;
    for(int i =0; i<N; ++i){
        cin >> A[i];
        ans ^= (A[i]*A[i]);
    }
    sort(A.begin(), A.end());
    for(int i =0; i<N-1; ++i){
        ans ^= (A[i]*A[i+1]);
    }
    cout << ans;
    
    return 0;
} // Bitmasking, Math
// X가 k번째로 큰 수라면 k번째가 제일 작고, l번째가 제일 큰 수인 조합은 2^(l-k-1)가지의 경우가 나온다.
// 이걸 생각하면 k와 k+1번째의 수를 곱한 것만 XOR에 반영이 된다. (홀수번 XOR해야 반영이 됨.)
// 또한 (k,k)는 딱 한 번씩만 나오므로 ans에 XOR이 반영된다.

 

요새 문제를 계속 풀고는 있는데 하나하나씩 정리하기가 힘들어서 모든 문제들을 이렇게 각잡고 정리하는게 아니라 일지에 요약식으로만 정리 및 리뷰하고 있었습니다. 이 문제도 오늘 풀고 일지에 적어두었는데, 문제가 재밌어서 이건 정리하게 되었습니다. 문제가 꽤 재밌었지만 난이도가 적어도 G3일줄 알았는데 G4였던 것은 좀 의외였습니다. 그래도 오랜만에 관찰이 매우 중요한 애드혹 + 수학 + 비트마스킹 문제를 풀어봤는데 매우 재밌었습니다.