[SWEA][D3][#02817] 부분 수열의 합

출처

• SW Expert Academy

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

문제

A1, A2, … , AN의 N개의 자연수가 주어졌을 때, 최소 1개 이상의 수를 선택하여 그 합이 K가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 2개의 자연수 N(1 ≤ N ≤ 20)과 K(1 ≤ K ≤ 1000)가 주어진다.

두 번째 줄에는 N개의 자연수 수열 A가 주어진다. 수열의 원소인 N개의 자연수는 공백을 사이에 두고 주어지며, 1 이상 100 이하임이 보장된다.

출력

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 부분 수열의 합이 K가 되는 경우의 수를 출력한다.

예제

입력

1
4 3
1 2 1 2

출력

#1 4

My Sol

T = int(input())
for tc in range(1, T+1):
    N, K = map(int, input().split())
    nums = list(map(int, input().split()))
    cnt = 0
    for subset in range(1 << N):
        sum_v = 0
        for j in range(N):
            if subset & (1 << j):
                sum_v += nums[j]

        if sum_v == K:
            cnt += 1

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

비트 연산자를 적용하면 쉽게 풀 수 있는 문제였다. N개의 자연수 수열이기 때문에 부분집합의 개수는 2^N개, 이 각각의 수를 range()를 이용해 개별적으로 확인한다.

이는 각각의 수이면서도 2진수로 변환하면 1이 위치한 특정 자릿수기 곧 nums의 항목을 꺼내오는 idx의 역할을 함을 이해하면 된다. 이 모든 경우의 수에 대해 완전탐색하면서, 비교하는 값인 K와 같다면 카운트를 +1 해주면 되겠다.

결과

PASS