SWEA 2817번 부분수열의 합 (Python, DFS, 완전탐색, D3)

SWEA 2817번 부분수열의 합 문제 바로가기

문제 접근

문제를 보면 N개의 수열중에서 합이 K가 되는 부분수열의 경우의 수를 구하라고 되어있다.
따라서 가장 쉬운 방법은 모든 경우를 진행해보는 것이다.
부분수열은 어떻게 만드느냐? 각 수열의 숫자를 포함하는지 안하는지로 나눌 수 있다.
따라서 DFS로 선택하는 경우, 안하는 경우로 나누어 진행하려고 한다.

문제 풀이

DFS는 아래와 같다.
종료조건에는 2가지를 넣었는데, 끝까지 인덱스를 증가시켰을 경우와 result가 K를 만족할 경우이다.
result가 K를 만족한다면 count를 1 증가시키고 그 함수를 종료시킨다.
이렇게 진행할 경우에 이미 result=K를 만족한 수열에 대해서 더 DFS를 진행하지 않아도 되기 때문에 시간적으로 단축시킬 수 있다.

종료조건은 위에서 설명한것과 같고, 이제 재귀함수를 보자
재귀함수는 둘 다 인덱스를 1증가시켜서 파라미터로 넘겨준다.
이렇게 넘길 때 하나는 부분 수열에 포함하는 재귀이고, 하나는 부분 수열에 포함하지 않는 재귀함수를 진행한다.

def dfs(i, result):
    global count
    if result == K: # 부분수열의 합이 K로 나온다면 i와 상관없이 count 1증가
        count += 1
        return
    if i == N:
        return
    dfs(i + 1, result + number[i])
    dfs(i + 1, result)

제출 코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
def dfs(i, result):
    global count
    if result == K:
        count += 1
        return
    if i == N:
        return
    dfs(i + 1, result + number[i])
    dfs(i+1, result)
for test_case in range(1, T + 1):
    N, K = map(int, input().split())
    number = list(map(int, input().split()))
    count = 0
    dfs(0, 0)
    print(f'#{test_case} {count}')