[SWEA] 4837. 부분집합의합 - Python

1부터 12까지의 숫자를 원소로 가진 집합 A가 있다. 집합 A의 부분 집합 중 N개의 원소를 갖고 있고, 원소의 합이 K인 부분집합의 개수를 출력하는 프로그램을 작성하시오.

해당하는 부분집합이 없는 경우 0을 출력한다. 모든 부분 집합을 만들어 답을 찾아도 된다.

예를 들어 N = 3, K = 6 경우, 부분집합은 { 1, 2, 3 } 경우 1가지가 존재한다.

 
 

[입력]
 

첫 줄에 테스트 케이스 개수 T가 주어진다.  ( 1 ≤ T ≤ 50 )
 

테스트 케이스 별로 부분집합 원소의 수 N과 부분 집합의 합 K가 여백을 두고 주어진다. ( 1 ≤ N ≤ 12, 1 ≤ K ≤ 100 )

 

[출력]
 

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

 

★ 시작하기 전에

비트 연산을 모르고 풀었을 당시... 너무 어려웠다. for문을 찾을 원소의 수만큼 돌려 겨우겨우 구현하는데.. 이게 맞는가 싶었다. 결론은 그 방법도 가능은 하되, 이 문제의 유형은 비트 연산자를 활용하면 쉽게 풀린다. 낯선 개념이지만 적어도 이 문제에서 만큼은 풀 수 있게 됬다.
지금 머릿속에는 비트 연산자를 활용하는 경우는 리스트 항목 중 부분 집합을 만들어 활용하는 경우라고 생각한다. 넣고 안넣고가 1, 0으로 나타내지기 때문에 그 집합 형식이 2진수를 나타낸다. 따라서 & 연산자로 포함여부를 알 수 있는 것!

 

import sys

input = sys.stdin.readline
T = int(input())
set_list = [ i for i in range(1, 13)]
m = len(set_list)

for case in range(1, T+1):
    n, k = map(int,input().split())
    ans = 0
    for i in range(1<<m):
        cnt = 0
        sum = 0
        for j in range(m):
            if i & (1<<j):
                sum += set_list[j]
                cnt += 1
        if cnt == n and sum == k:
            ans += 1
    print('#{} {}'.format(case, ans))

이런 문제 외에도 어떤 경우에 적용할 수 있는지 궁금하다.