2일차 - 부분집합의 합

def howmany1(n):
    cnt = 0
    while(n != 0):
        if(n & 1):
            cnt += 1
        n = n >> 1
    
    return cnt

t = int(input())
answer = list()

for _ in range(t):
    a = [1,2,3,4,5,6,7,8,9,10,11,12]
    n, k = map(int, input().split())

    subset = list()
    for i in range(1 << 12):
        var = list()
        if howmany1(i) != n:
            continue
        
        for j in range(12):
            if(i & (1 << j)):
                var.append(a[j])
        
        subset.append(var)

    cnt = 0
    for i in subset:
        if sum(i) == k:
            cnt += 1

    answer.append(cnt)

for i in range(t):
    print(f"#{i+1} {answer[i]}")

 

- howmany1(n)

자연수 n을 이진수로 변환했을 때 1이 몇 개 들어있는지 반환하는 함수!

들어온 값을 1씩 right 연산 해주면서 1과 & 연산으로 비교하여 얻었다.. 만든 이유는 부분집합 원소 개수가 아닌 걸 걸러내기 위해서..

 

아직은 역량 부족으로 거의 brute-force 형식으로 찾은 것 같다

그래도 SWEA 강의에서 배운 비트를 통해 부분집합을 생성하는 알고리즘을 이해하고 사용해봐서 의미있던 문제인듯!