백준_1182번_부분수열의 합

백준 1182번 부분수열의 합

부분수열의 합

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

나의 풀이

우선 모든 경우의 수를 다 탐색해야된다고 생각했음.
근데 이제 어떻게 탐색을하냐가 문젠데, 너무 무식하게 n개씩 더하는것보다는 그냥 트리 탐색하듯이
계속해서 이곳저곳 탐색하면 될것같았음. 이진트리로

그래서 DFS를 이용한 재귀탐색으로 코드를 짰고 중요한 부분은 bool 변수로 선언한 flag 인데, 이 변수를 언제 False로 바꾸고 또 언제 True로
바꿔야하는지 정확히 캐치를 못해서 좀 해멨던 문제였다...

코드

import sys

input = sys.stdin.readline

N, S = map(int, input().split())

list_ = list(map(int, input().split()))
flag = False   # 트리를 왼쪽으로(즉, 자기 자신 포함 안시키고 그냥 뛰어넘기할때) 내려갈때 S를 또 카운트해주면 안되니까 필요한 변수
cnt = 0        # 문제에서 주어진 합 S를 만족할때마다 카운트해주는 변수

def DFS(level, sum_):
    global flag, cnt # 전역변수의 값을 함수내에서 다뤄야하니 global로 선언

    if flag==True and sum_ == S: #flag가 True이고(왼쪽 트리를 타고 온게 아니고) 숫자들의 sum이 S를 만족할때 cnt값을 하나 올려줌
        cnt += 1
    
    if level == N-1:	#트리의 깊이가 최대치에 도달하면 return
        return
    
    else:
        flag = False	#왼쪽 자식 트리로 넘어갈땐 그냥 건너뛰기를 하는것이기 때문에 항상 flag를 False로 바꿔주고 들어가야됨.
        DFS(level+1, sum_)
        
        flag = True		#그리고 나서 바로 다시 flag를 True로 바꿔주면서 오른쪽 트리 탐색. 이때 조건 만족하면 cnt++
        DFS(level+1, list_[level+1]+sum_)

DFS(-1, 0)

print(cnt)