SWEA 4837 부분집합의 합 (python)

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

 

[파이썬 S/W 문제해결 기본] 2일차

2021.04.21 - [Algorithm] - SWEA 4836 색칠하기 (python)

2021.04.19 - [Algorithm] - SWEA 4837 부분집합의 합 (python)

2021.04.21 - [Algorithm] - SWEA 4839 이진탐색 (python)

2021.04.21 - [Algorithm] - SWEA 4843 특별한 정렬 (python)

문제

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

풀이

T = int(input())

def subset(info):
    # N과 K 값을 임의로 설정한 리스트에서 하나씩 받아옴
    N = info[0]
    K = info[1]
    # 1부터 12까지의 범위의 리스트 설정
    A = [i for i in range(1,13)]

    # 전체 초기값 설정
    numbers = []
    # 부분집합 구하는과정
    for i in range(1<<12):
        sub_numbers = []
        for j in range(12):
            if i&(1<<j):
                # 부분집합 리스트를 생성
                sub_numbers.append(A[j])
        # 만약 부분집합 리스트의 길이가 원하는 N 이라면 전체 리스트에 삽입
        if len(sub_numbers) == N:
            numbers.append(sub_numbers)
    # 카운트 초기화
    count = 0
    # 내장함수 sum 대신 total로 합을 구해서 원하는 값이 나오면 카운트
    # 내장함수 사용시 위의 반복문에서 종료 가능
    for i in range(len(numbers)):
        total = 0
        for j in numbers[i]:
            total += j
        if total == K:
            count += 1

    return count


for tc in range(1, T+1):
    info = list(map(int, input().split()))
    result = subset(info)
    print("#{} {}".format(tc, result))