[SWEA|파이썬] 2817. 부분 수열의 합 (D3)

문제

https://tinyurl.com/2ozhj4hf

SW Expert Academy

 

 

🐍파이썬

def dfs(depth, hap):
    global ans
    if hap == k:
        ans += 1
        return
    if depth == n:
        return
    a = arr[depth]
    dfs(depth+1, a+hap) #해당 수 선택하는 경우
    dfs(depth+1, hap) #해당 수 선택하지 않는 경우

T = int(input())
for test_case in range(1, T + 1):
    ans = 0
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    ans = 0
    dfs(0, 0)
    print("#{} {}".format(test_case, ans))

이전에 풀었던 [SWEA|파이썬] 5215. 햄버거 다이어트 (D3) 와 동일한 방식으로 풀었다. 

원하는 수의 합에 도달할 때까지 깊이우선탐색을 하는 문제이다.

원하는 수의 합인 hap과 k가 동일하다면 ans에 1을 더해 횟수를 카운트해주었다.

또한 더 이상 깊이 들어갈 수 없을 때는(=마지막 노드까지 탐색했는데도 hap==k를 찾지 못한 경우)에는 ans+1 없이 return을 진행했다.

arr[depth]의 수를 선택하는 경우와 그렇지 않은 경우 모두 dfs를 진행해 모든 경우의 수를 탐색하였다.

 

 

 

 

 

👇 비슷한 풀이방식의 문제 더보기

[프로그래머스 | 파이썬 / 자바스크립트] 타겟 넘버(깊이/너비 우선 탐색(DFS/BFS)/level 2)

[프로그래머스 | 파이썬 / 자바스크립트] 타겟 넘버(깊이/너비 우선 탐색(DFS/BFS)/level 2)