[SW Expert Academy] 4837. 부분집합의 합

4837. 부분집합의 합

---

문제)

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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

 

풀이)

T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    li = [z for z in range(1, 13)]
    answer = 0
 
    for i in range(1 << 12): # 모든 부분집합
        total = 0
        cnt = 0
        for j in range(12):
            if i & (1 << j):
                cnt += 1
                total += li[j]
        if total == k and cnt == n:
            answer += 1
    print(f"#{_ + 1} {answer}")
 

 

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.