4837. [파이썬 S/W 문제해결 기본] 2일차 - 부분 집합의 합

D3

Problem

SW Expert Academy 부분집합의 합

SW Expert Academy

---

Solution

1. Bit Masking을 이용하여 각 자리에 숫자가 있는지 확인하는 방식을 이용한다.
2. 이 중 길이가 K이면서, N번째 부분 집합을 카운트한다.

Bit Masking
bit 연산을 통해 각 자리에 숫자가 있는가를 확인하는 방법

솔직히 나도 한번에 이해가 되지 않았다.

예를 들어서, 3이라는 숫자가 있으면, 2진수로 0b0011로 표현할 수 있다.
이는 첫 번째, 두 번째 자리에 1, 세 번째, 네 번째 자리에 0이 있어 & 연산을 하면 첫 번째와 두 번째 자리에 숫자를 찾을 수 있다.

이와 같은 방식으로 부분 집합 {1,2} 를 찾을 수 있으며, 이를 이용하면 모든 경우의 수의 부분 집합을 구할 수 있다.

 

Code

for test_case in range(1, int(input()) +1):
    N, K = map(int, input().split())
    A = list(range(1, 13))
    count = 0
    # N개 까지의 부분집합 개수까지 반복
    for i in range(1<<12):
        resu = 0
        arg = 0
        # 0부터 N-1 까지
        for j in range(12):
            # 부분집합이 존재한다면
            if i & (1<<j):
                # 값의 합과 갯수
                resu += A[j]
                arg += 1
        if resu == K and arg == N:
            count += 1
    print(f'#{test_case} {count}')

<부족한 부분은 댓글로 남겨주시면 저에게 도움이 됩니다!>