[백준] BOJ 23630 : 가장 긴 부분 수열 구하기

[백준] https://www.acmicpc.net/problem/23630

23630번: 가장 긴 부분 수열 구하기

일단 문제의 조건은 문제 자체에도 적혀있지만 풀어서 적으면 아래와 같습니다.

 

1. 부분 수열의 원소들을 전부 bitwise AND를 했을 때 0이 되면 안됨

2. 부분 수열은 원래 수열에서 위치를 바꾸지 않고 유지해야 합니다. 또한, 동일한 위치의 원소를 여러번 사용하는 것도 불가능

3. 가능한 제일 긴 부분 수열의 길이를 출력

 

그렇다면 일단 bitwise AND를 했을 때 0이 안 되는 경우가 어떤건지를 생각해봅시다. 먼저, AND 연산은 두 비트가 1일 때 1, 아니면 0이 됩니다. 그리고 bitwise AND 결과가 0이 아니라면 어느 비트는 1이라는 거겠죠. 결과에서 어느 비트가 1이라면 해당 부분수열의 원소들의 해당 비트가 모두 1이어야 합니다.

 

이를 알아챘다면, 각 비트에 대해서 켜져있는 값들만 가지고 부분수열을 만들면 bitwise AND 결과가 0이 아닌 걸 알 수 있습니다. 그래서 모든 비트들에 대해서 켜져있는 값들의 개수를 구하고 그 중에서 제일 많은 개수를 정답으로 출력하면 됩니다.

 

코드는 아래와 같습니다. 시간복잡도는 \(O(N\log{1000000})\) 입니다. 다만 \(\log{1000000}\)은 \(30\)보다 작으므로 그냥 상수처럼 보셔도 됩니다. 

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    ll N, M;
    cin >> N;
    vector<ll> a(N);
    for(int i =0; i<N; ++i){
        cin >> a[i];
    }
    
    ll ans = 0;
    
    for(ll i =0; i<30; ++i){
        ll val = ((ll)1 << i);
        ll tmp = 0;
        for(int i =0; i<N; ++i){
            if(val&a[i]){
                ++tmp;
            } // 해당 비트가 켜졌을 시
        }
        ans = max(ans, tmp);
    } // 2^30 > 1'000'000
    
    cout << ans;
    
    return 0;
} // O(NlogN)

 

이를 보고 저는 처음에 문제의 조건을 잘못 이해했어서 bitwise AND를 했을 때 0인 아닌 LIS를 찾아야 하는건가 싶었습니다. 그래서 \(O(N\log{N})\) LIS를 활용해서 풀었었는데 당연히 틀렸습니다. 조건을 제대로 읽어야 한다는 교훈을 주는 문제였습니다.