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

SW Expert Academy 4837번 부분집합의 합 문제는 1부터 12까지의 숫자를 원소로 가진 집합 A의 부분집합 중 N개의 원소를 갖고 있고, 원소의 합이 K인 부분집합의 개수를 구하여 출력하는 문제이다. 난이도는 D3이고, 2차원 리스트 자료구조에 관한 문제이다.

 

SW Expert Academy 4837번 부분집합의 합 문제 정보

자료구조 분류

- 리스트 (2차원)

난이도

- D3

 

부분집합의 합 문제 요약

• 부분집합의 원소의 수 N의 범위는 1 이상 12 이하이다.
• 부분집합의 합 K의 범위는 1~100이다.
• 해당하는 부분집합이 없는 경우 0을 출력한다.

문제 풀이 과정

• 집합 A의 부분집합을 모두 구하여 2차원 리스트인 subsetA [][]에 저장한다.
• 부분집합 subsetA를 모두 탐색하여 원소의 수가 N개, 원소의 합이 K일 때 카운트한다.
• 테스트 케이스 번호, 조건에 만족하는 부분집합의 개수를 출력한다.

코드 및 설명

• subsetA [][] - 집합 A의 부분집합을 저장한 2차원 리스트
• cnt - 조건에 만족하는 부분집합의 개수

A = [i for i in range(1, 13)]
subsetA = [[] for _ in range(2**12)]

# 집합 A의 부분 집합 구하기
for i in range(1 << 12):
    for j in range(12):
        if i & (1 << j):
            subsetA[i].append(A[j])

T = int(input())
for tc in range(T):
    cnt = 0
    N, K = map(int, input().split())
    for i in range(len(subsetA)):
        if len(subsetA[i]) == N and sum(subsetA[i]) == K:
            cnt += 1
    print("#%d %d"%(tc+1, cnt))

---

SW Expert Academy 4837번 부분집합의 합 문제는 2차원 리스트 자료구조에 관한 문제이며 파이썬을 사용하였다. 난이도는 D3인데 아마 부분집합을 구하는 알고리즘을 구현하는 것이 조금 복잡하기 때문이지 않을까 싶다. 파이썬 부분집합 알고리즘이 여러 개인데 더 공부해서 따로 포스팅해야겠다.