[SWEA 코딩] 부분 수열의 합 - PYTHON #2817

소스 코드

def dfs(idx,cur_sum):
    global res

    if cur_sum == k:
        res += 1
        return

    if cur_sum > k:
        return

    if idx == n:
        if cur_sum == k:
            res += 1

        return

    dfs(idx+1,cur_sum + arr[idx])
    dfs(idx+1,cur_sum)

    return

T = int(input())

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

    n,k = map(int,input().split())

    arr = list(map(int,input().split()))

    res = 0

    for q in range(n):
        dfs(q+1,arr[q])

    print('#{} {}'.format(tc,res))

 

---

해결 방법

1. 단순 DFS로 해결(n의 값이 <=20 이지만, 2(선택 or 선택 X)의 20승 정도가 최대 값이라 판단하여 문제 없을 것이라 생각)

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.