[SWEA 2817번] 부분 수열의 합 - 파이썬(python)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7IzvG6EksDFAXB

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가 되는 경우의 수를 출력한다.

풀이

• 앞서 풀이한 swea 1486번 장훈이의 높은 선반과 매우 유사한 문제이다.
• 조합으로 가능한 합을 구하고 그 합이 제시된 숫자 K와 동일하다면 카운팅하는 식으로 풀이했다.
• 앞선 문제와 다른 형식으로 풀이하고 싶어서 다르게 풀어봤다.
• start라는 임의의 수를 이용하여 이미 선택한 것은 제외하고 답을 구하는 식이다.
• 마지막까지 계산할 필요없이 K와 같은 값이라면 cnt+1, 큰값이라면 리턴했다.

코드

def dfs(start,summ):
    global cnt
    if summ > K:
        return
    if summ == K:
        cnt += 1
        return
    for i in range(start,N):
        dfs(i+1,summ + A[i])

T = int(input())
for test_case in range(1, T + 1):
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    cnt = 0
    dfs(0,0)
    print(f'#{test_case} {cnt}')