[파이썬] 백준 30015 : 학생회 뽑기 (골드3)

[파이썬] 백준 30015 : 학생회 뽑기 (골드3)

30015번: 학생회 뽑기

---

문제

---

풀이

방향성 생각

• 20자리 비트를 모두 체크한다.
• 100(2) > 11(2). 비트의 자리수가 커지면 이전 비트들을 모두 합해도 더 크다. (등비수열 합)
• MSB부터 순차적으로 확인한다.
• 특정 비트 자리수에서 1이 K개 이상이면 그 숫자들을 모으고 낮은 비트 자리수 체크를 반복

전체코드

N,K = map(int,input().split())
info = list(map(int,input().split()))

answer = 0
for i in range(19,-1,-1):
    temp = []
    for num in info:
        if num&(1<<i):
            temp.append(num)
    if len(temp) >= K:
        answer += 1<<i
        info = temp
print(answer)

• 특정 자리수의 1이 K개가 넘어가면, 해당 숫자들은 모두 AND연산으로 1을 만들 수 있다.
• 이 때 answer에 값을 업데이트 해주고, info를 선택한 숫자들로 업데이트 한다.

코멘트

.