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

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

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

 

---

풀이 과정

---

1. & 연산의 경우 두 비트가 모두 1일때만 1, 아닐때는 0으로 설정한다는 점을 이용
2. 따라서, 우선 비트의 개수를 저장해 둘 배열을 만들어 둔다.
   1. array[0] : 0번째 자리에서 비트 1의 개수, ..
3. 각각의 수를 모두 2진수로 바꾼 다음 각 자리를 검사하면서 비트가 1인 경우, 배열의 해당 자리 값을 1 증가시킨다.
4. &연산의 결과가 0이 되지 않으려면, 연산을 하는 값들의 비트중 하나라도 모두 1이 나와야 한다. 따라서 1이 가장 많이 나온 자리를 찾아주어야 하므로, 배열의 최댓값을 구한다.

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())
sequence = list(map(int, input().split()))
bit_count = [0] * 32

def calc_bit(a):
    temp = a
    n = 0
    while temp > 0:
        bit_count[n] += (temp % 2)
        temp = temp // 2
        n += 1

for item in sequence:
    calc_bit(item)

print(max(bit_count))