[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

def tree(i, ssum):
    if ssum >= K:
        if ssum == K:
            global cnt
            cnt += 1
        return

    if i == N:
        return

    tree(i+1, ssum)
    tree(i+1, ssum+arr[i])

T = int(input())
for tc in range(1, T+1):
    N, K = map(int, input().split())
    arr = list(map(int, input().split()))
    cnt = 0
    tree(0, 0)

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

tree의 부분집합을 이용하여 가지치기를 하면서 수열의 합을 구하는 문제였다. 배열이 정렬되지 않고, 값이 같은 경우에 중복을 허용하기 때문에 처음에는 어떻게 풀어야하나 했지만, 트리를 이용하면 쉽게 접근할 수 있었다.

결과

PASS