[파이썬] 4837. 부분집합의 합

swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

※ 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

 

🧵 나의 풀이

 

# 실패 😥
from itertools import combinatations
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    A=set(range(1, 13))
    N, K = map(int, input().split())		# 원소 갯수, 원소의 합
    ans=list(set(combinations(A, N)))
    cnt=0
    
    for i in ans:        
        if sum(i) == K :
            cnt+=1
            break
    
    print('#%d %d' %(test_case, cnt))

 

 

길이가 K인 부분집합의 갯수가 제대로 나오는데..

부분집합의 합 부분을 잘못 했나봐..

 

# 성공 ✨
from itertools import combinations
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    A=list(range(1, 13))					# 1부터 12까지
    N, K = map(int, input().split())		# 원소 갯수, 원소의 합
    ans=list(set(combinations(A, N)))		# 조합으로 리스트 A를 N길이를 가지는 부분집합을 리스트에 저장
    cnt=0
    
    for i in ans:        
        if sum(i) == K :					# 부분집합의 합이 K면 cnt를 1증가
            cnt+=1
    
    print('#%d %d' %(test_case, cnt))

 

왜 안 돼나 했더니 if sum(i)==K가 한 번만 실행되도록 해놨었네;

조합을 이용해서 풀었다.

 

 

🎗 다른사람 풀이

 

TC  = int(input())
num = [1,2,3,4,5,6,7,8,9,10,11,12]
Len = len(num)

#부분집합 구하기
lst = []
for i in range(1<<Len):
    sub_lst = []
    for j in range(Len):
        if i & (1<<j):
            sub_lst.append(num[j])
    lst.append(sub_lst)


for tc in range(1, TC+1):
    N, K = map(int, input().split())		# 원소 갯수, 원소의 합

    #길이 맞는 리스트 구하기
    len_lst = []
    for i in lst:
        if len(i) == N:
            len_lst.append(i)


    #합 일치 유무 확인
    result = 0
    for i in len_lst:
        if sum(i) == K:
            result += 1

    print('#%s %d'%(tc, result))

 

처음에 lst에 num리스트를 기반으로 부분집합을 만든다(이 문제에서 2^12개만큼 만들어진다).

lst를 반복하면서 길이가 N인 부분집합을 리스트 len_lst에 넣는다.

리스트 len_lst를 반복하면서 원소의 합이 K인 부분집합의 갯수를 센다.