SWEA - 부분 집합의 합 [Python]

 문제

 

 집합 A는 1부터 12까지의 숫자를 원소로 가지고 있다. 이 때, 원소의 개수가 N개이며 그 합이 K인 부분집합의 개수를 출력한다.

 

 문제 상황

 

- 부분 집합을 완전 탐색으로 전체 조사해야한다.

 

 해결 전략

 

- 원소의 개수가 12개 이므로 부분집합의 총 수는 공집합을 포함하여 2^12 = 4096으로 크기가 작기 때문에 완전탐색으로 하여도 문제가 없다. 완전탐색하며 합이 K와 같은지를 판별하면 된다.

 

 코드

 

# 부분 집합의 집합을 찾는 함수
def subset(lst):
    n = len(lst)
    # 부분 집합들을 담을 집합
    result = []
    # 2^n 까지 순회 (0, 1, 10, 11, ... ) 
    # -> (공집합, 마지막 요소만 포함, 마지막에서 2번째 요소만 포함, ...)
    for i in range(1<<n):
        # 새로운 i에서 부분집합을 초기화
        temp = []
        # 전체집합 lst의 원소를 첫번째부터 마지막까지 본다
        for j in range(n):
            # 1<<3 = 8
            # 예를 들어, i가 11로 고정되어 있으면 1<<j는 1을 0, 1, 2, .. 로 증가시키면서
            # i가 1인 부분에서만 요소를 추가한다. 이 때 j는 lst의 j번째 요소를 의미한다.
            if i&(1<<j):
                # i의 비트 자리가 1인 요소를 부분집합에 담는다.
                temp.append(lst[j])
        # 완성된 부분집합을 부분집합의 집합에 담아준다.
        result.append(temp)
    return result
 
A = [i for i in range(1,13)]
T = int(input())
subset_A = subset(A)
for idx in range(T):
    N, K = map(int, input().split())
    num_Subset = 0
    for i in range(len(subset_A)):
        # 부분집합의 개수가 N이면서 합이 K인 값의 개수를 더해준다.
        if sum(subset_A[i]) == K and len(subset_A[i]) == N:
            num_Subset += 1
    print(f"#{idx+1} {num_Subset}")

 

 

 해설

 

- subset을 찾는 함수를 만들어 사용하였다. 부분집합의 집합을 만드는 함수를 만들어 전체 조사하였고, 이 때에 비트 연산자를 활용하였다. 예를 들어, 원소가 4개인 부분집합의 경우 1<<4를 하면 0 ~ 1111 까지 순회하며 각 자리가 1인 부분의 원소를 부분집합에 담았다. 1<<j 는 j가 0에서 부터 3까지 이므로 1, 10, 100, 1000의 경우, 즉 첫번째 요소부터 네번째 요소까지를 검색하여 (첫번째 요소가 1인가?) (두번째 요소가 1인가?) 등을 계속 체크하여 값을 넣어준다.

 

 새로 학습한 것 & 실수 

 

- subset 함수를 만들 때에 temp 폴더와 result 폴더를 넣는 위치가 고민되었다. 또 코드에 12번째, 16번째 줄이 이해하기 힘들었다.

 

 

출처 - https://swexpertacademy.com/main/