백준 1182번 부분수열의 합

문제 설명

 

이진 트리를 사용하여 해당 정수를 더할지 말지를 정했다. 이진 트리에서 왼쪽으로 가면 정수를 더하지 않는 것이고 오른쪽으로 가면 정수를 더하는 방식으로 생각했다.

수열이 {1,2,-3}일 때

cur은 현재 depth을 뜻하고 total은 수열의 합을 뜻한다. cur이 depth인 S와 같아졌을 때 해당 수열의 합이 N과 같으면 count를 1 더하고 함수를 종료한다. cur이 height보다 작을 경우 이진 트리의 왼쪽으로 갈 경우와 오른쪽으로 갈 경우를 나누어 함수를 호출한다.

 

 

전체 코드

arr = []
count = 0
N = 0
S = 0

def func(cur,total):
    global count
    global N
    global arr
    global S

    if cur == S:
        if total == N:
            count += 1
        return

    func(cur+1,total)
    func(cur+1,total+arr[cur])
    return

def main():
    global arr
    global count
    global N
    global S

    tmp = list(map(int,input().split()))
    S = tmp[0]
    N = tmp[1]

    arr = list(map(int,input().split()))
    func(0,0)
    if N == 0:
        count -= 1
    print(count)
    return


if __name__ == "__main__":
    main()전체 코드