[SWEA][D3][#04837] 부분집합의 합

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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

My Sol

T = int(input())
for tc in range(1, T+1):
    L = 12
    N, K = map(int, input().split())

    while L > K:  # L 범위 줄이기
        L -= 1

    A = [i for i in range(1, L+1)]
    result = 0
    for subset in range(1<<L): # 부분집합 조회
        cnt = 0
        sum_v = 0

        for j in range(L):  # L에 대하여
            if subset&(1<<j):
                sum_v += A[j]
                cnt += 1

        if (cnt==N) and (sum_v==K): # cnt가 N개이고 합이 K라면
            result += 1

    print(f'#{tc} {result}')

비트를 활용하는 문제였다. 최초에 A 집합은 1부터 12까지 나열되는 수이다. 이는 변하지 않지만 조회하는 범위를 줄이기 위해 L을 줄이는 로직을 넣었다. 만약 구해야하는 합계 K가 A 내의 어떠한 한 값보다도 작다면, 그 뒤에서는 합계가 K와 같은 부분집합이 절대 나올 수 없으므로 L이 K보다 큰 동안은 L을 줄이는 것으로 하였다.

이렇게 줄인 L을 이용해 축소된 A 리스트를 만들고, 비트 연산을 이용해 부분집합인 subset의 2진수 표현에서 각 자리에 1이 있는지 없는지 여부를 확인하였다. 만약 1이 있다면 subset&(1<<j)는 True가 되므로 이때의 자릿수를 인덱스로하여 A 리스트에서 항목을 꺼내 합계변수에 더해준다. 그리고 부분집합의 항목의 개수를 세는 cnt 변수도 하나 늘려준다.

이렇게 subset에 대한 연산을 모두 마치면 cnt가 원하는 개수가 맞는지, 합계가 원하는 합계가 맞는지 판단하고, 이 조건에 해당된다면 결과 출력 변수 result를 하나 늘려준다. subset이 조건에 해당하는 subset이라는 뜻이다.

결과

PASS