자료구조&알고리즘/알고리즘 - 대회 알고리즘

[알고리즘 문제 풀이][비트마스킹] 백준 23630번 - 가장 긴 부분 수열 구하기

초코쨔응 2024. 11. 24. 15:48

풀이 참고 블로그: [Python] 23630번 가장 긴 부분 수열 구하기

 

- 문제 설명: 23630번: 가장 긴 부분 수열 구하기  

N개의 자연수로 이루어진 수열 A = {A1, A2, ..., AN} 이 주어집니다.

다음 조건을 만족하는 가장 긴 부분 수열을 찾아야합니다.

(1) Ai1 & Ai2 & ... & Aim 이 0 이 아니어야 합니다. (선택한 수들끼리 AND 비트 연산을 했을 때 겹치는 비트가 1개 이상이 있어야합니다.)

(2) 1 <= i1 < i2 < ... < im <=N 이어야합니다. (A 내에서 수를 선택할 때 겹치지 않게 순서대로 하나씩 선택해야합니다.)

 

N 의 최대 크기는 1,000,000 이며, Ai 의 최대 수 또한 1,000,000입니다.

 

 

- 문제 풀이:

조건을 만족하는 가장 긴 부분 수열을 찾는다고 하면, 백트래킹을 먼저 생각해볼 수 있습니다.

하지만, N이 1,000,000 이기 때문에 이 크기의 수열을 백트래킹을 한다고 하면 시간 초과를 피할 수 없습니다.

따라서 시간 안에 들어올 수 있는 다른 측면의 해답이 필요합니다.

 

Ai 의 최대값이 1,000,000 이기 때문에 비트로 표현하면 2^20 (=1,048,576) 안에 표현할 수 있습니다. 

19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

 

문제의 조건 (1) 을 만족하려면 겹치는 비트가 있어야하는데, 0~19번째 비트 중에서 수들 간에 가장 많이 겹치는 비트를 찾으면 그 수들을 선택했을 때 정답이 될 것입니다.

따라서 각 수마다 0번~19번 비트 중에 어떤 비트를 가지고 있는지를 세고, 최종적으로 0번~19번 비트마다 수열의 수들이 가장 많이 공통적으로 갖고 있는 비트를 출력합니다.

 

- 코드 (Python): 

n=int(input())
a=list(map(int,input().split()))
cnt=[0]*20
for i in range(n):
    for j in range(20):
        if a[i]&(1<<j):
            cnt[j]+=1
ans=0
for i in range(20):
    if ans<cnt[i]:
        ans=cnt[i]
print(ans)

 

- 실수 포인트 & 반례:

문제의 예제 외에 필요한 반례는 없었습니다

반응형