[Python] 23630번 가장 긴 부분 수열 구하기

 

 

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

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

---

 

24/01/04

 

 

비트마스킹의 아이디어를 사용하는 애드 혹 문제이다.

---

 

문제 접근 방식:

 

 

처음에 아주 나이브하게 접근해서 틀렸습니다를 받았다.

 

이 접근 방식은, 모든 배열의 값을 AND연산했을 때 0이 나온다면 (배열의 길이)-1이 답이 된다는 접근이었다.

 

생각해 보니 정말 틀린 접근 방식이었고, 이 문제는 곧 비트별로 생각해야 풀 수 있음을 깨달았다.

 

AND연산을 했을 때 어떠한 비트가 0이 나왔다는 뜻은, 그 비트가 0이 되는 어떠한 수가 있다는 뜻이다.

 

즉, AND연산을 했을 때 0이 되었다는 뜻은 모든 비트가 0이 되었다는 뜻이고, 모든 비트마다 0이 되도록 만드는 어떠한 수가 존재한다는 뜻이다.

 

따라서, 특정 비트만 보았을 때 0이 되도록 만드는 수를 제외한 애들만 모아놓는다면, 그 비트만큼은 0이 되지 않기 때문에 AND연산을 취해도 0이 되지 않는다.

 

따라서, 모든 수마다 다음과 같은 일을 했다.

 

그 수의 $0$번째 비트, $1$번째 비트,... $30$번째 비트까지 모두 확인해서, 그 비트가 $1$이라면 비트 배열에 +1을 해준다.

 

즉, $0$번째 비트가 $1$로 켜져 있는 수는 총 몇 개인지, $1$번째 비트가 $1$로 켜져 있는 수는 총 몇 개인지, 그렇게 해서 $N$번째 비트가 $1$로 켜져 있는 수는 총 몇 개인지 세주었다.

 

만약 우리가 $1$번째 비트가 $1$로 켜져있는 수로만 부분 수열을 구성한다면 $1$번째 비트는 모두 $1$이므로 그 비트만큼은 절대로 AND연산을 취해도 0이 되지 않는다.

 

따라서, 0이 되지 않도록 하는 부분 수열을 구성할 수 있는 것이다.

 

즉, 우리는 이 부분 수열 중 길이가 가장 긴 것을 원하므로, 저렇게 $N$번째 비트가 $1$로 켜져 있는 수들 중에서 가장 많은 개수를 차지하는 수는 총 몇 개인지가 이 문제의 답이 될 것이다.   

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 23630번 가장 긴 부분 수열 구하기
# 애드 혹
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().rstrip().split()))
total = A[0]
for i in range(1, N):
    total &= A[i]
if total == 0:
    B = [0 for _ in range(30)]
    for i in A:
        k = 0
        for j in bin(i)[::-1]:
            if j == 'b':
                break
            if j == '1':
                B[k] += 1
            k += 1
    print(max(B))
else:
    print(N)