[Python, 파이썬] SWEA 2817. 부분 수열의 합

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

 

 

def DFS(i, current_value):

    global answer # 합이 K개가 되는 경우의 수

    
    if(current_value > K): # 합이 K를 넘었을 시
        return

    if(current_value == K): # 합이 K일 시
        answer += 1
        return

    if(i==N): # 수열 전체 검사 완료 시
        return

    DFS(i+1, current_value) # 현재 자연수 미선택
    DFS(i+1, current_value+A[i]) # 현재 자연수 선택


T = int(input()) # 테스트케이스 수 T

for test_case in range(1, T+1):

    N, K = map(int, input().split()) # 자연수의 개수 N, 합 K
    A = list(map(int, input().split())) # 수열 A

    answer = 0
    DFS(0, 0) #
            
    print("#%d %d" %(test_case, answer))

 

 

 

[문제풀이]

---

 

DFS+백트래킹으로 푸는 문제.

N개의 수 중 무작위로 골라서 합이 K가 되면 된다.

 

SWEA 5215번 햄버거 다이어트와 매-우 유사한 문제다.

고를 수 있는 개수도 정해져 있지 않고 합만 K개가 되면 되므로 모든 경우의 수를 확인해야 한다.

 

BFS(i+1, current_value) # 현재 자연수 미선택
BFS(i+1, current_value+A[i]) # 현재 자연수 선택

 

그래서 이렇게 현재 자연수 선택/미선택으로 백트래킹을 돌리면 끝!

이때 자연수를 찾을 시 경우의 수에 +1하고 DFS를 끝낸다.

또, K보다 크게 되거나 모든 자연수를 다 탐색했을 경우도 그대로 DFS를 끝낸다.