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

출처

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


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

 

입력
3
3 6
5 15
5 10

출력
#1 1
#2 1
#3 0

 

Pass 코드

from itertools import combinations

T = int(input())
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
for t in range(T):
    N, K = map(int, input().split())
    C = list(combinations(A, N))
    result = 0
    for c in C:
        if sum(c) == K:
            print(c)
            result += 1

    print("#{} {}".format(t+1, result))

 

해설

2021.05.26 - [파이썬 Python] - [파이썬 Python] itertools , 순열과 조합 (permutations, combinations)

[파이썬 Python] itertools , 순열과 조합 (permutations, combinations)