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

#파이썬 풀이

##질문은 댓글

 

arr = [1,2,3,4,5,6,7,8,9,10,11,12]
n=len(arr)
new_arr=[]
for i in range(1<<n): #부분집합의 개수만큼 실행
    new2=[]
    for j in range(n):
        if i&(1<<j):
            new2.append(arr[j])
    new_arr.append(new2)

testCase = int(input())
for i in range(testCase):
    check_list = [] #n개의 원소를 가진 부분집합이 들어갈 자리
    check = 0
    n_m = [int(x) for x in input().split(" ")] #0:부분집합개수 1:합이몇이되는지
    for j in range(1<<n): #부분집합 검사하기
        if len(new_arr[j]) ==n_m[0]: #문자열 길이가 숫자갯수랑 같을때
            check_list.append(new_arr[j])
    for k in range(len(check_list)):
        if sum(check_list[k]) == n_m[1]:
            check += 1
    print('#'+str(i+1)+' '+str(check))

 

변수 설명 :

arr = 1-12를 원소로 가진 집합 리스트

n = arr 의 길이 (12)

new_arr = 부분집합들이 들어갈 리스트

new2 = 부분집합의 원소를 만들어주고 이걸 new_arr에 append 해주는 역할

testCase = 테스트 케이스의 수

check_list = n개의 원소를 가진 부분집합이 들어갈 자리

check = n개의 원소를 가진 부분집합중 합이 m 인것들의 개수를 체크해주는 변수

n_m = n이란 m

 

문제를 보면 이렇게 하면 되겠구나 하는게 있다가도 정작 해보면 어려운것들이 있다

그래도 내가 원하는 방식으로 구현한듯 ! :-)