백준 1182: 부분수열의 합

관련 링크 : https://www.acmicpc.net/problem/1182

백준 1182 : 부분수열의 합

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

입력

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

5 0
-7 -3 -2 5 8

출력

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

1

풀이

부분 수열을 만들 때 사이 간격이 일정해야 하는 줄 알고 시도했다가 풀지 못했다. 여기저기 찾아봐서 그게 아님을 알아채고 풀 수 있었다. 첫 번째 풀이로 모든 경우의 수를 고려하기 위해 Combination을 이용했다. 단순히 하나부터 주어진 크기까지 늘려가면서 Comb를 이용해 모든 경우의 수를 구하고 최종적으로 주어진 s와 같은지 확인했다.

import sys
from itertools import combinations

input = sys.stdin.readline
n, s = map(int, input().strip().split())
number_list = list(map(int, input().strip().split()))

def brute_force(n, s, number_list):        
    count = 0
    for i in range(1,n+1):
        per = combinations(number_list, i)
        for j in list(per):
            if sum(j) == s:
                count += 1
    return count

print(brute_force(n, s, number_list))

다른 방법으로 DFS를 쓰는 방법이 있었다. DFS가 뭔지도 몰랐는데, 참고 코드가 내 기준으론 직관적이지 않아서 조금 수정했다.

import sys
from typmr

input = sys.stdin.readline
n, s = map(int, input().strip().split())
number_list = list(map(int, input().strip().split()))

# DFS를 이해하기 위해서 추가한 부분
# class Decorator:
#     def __init__(self, func) -> None:
#         self.num = 0
#         self.func = func

#     def __call__(self, *args, **kwargs):
#         print(f'Call {self.num}, S: {args[0]}, List: {args[1]}')
#         self.num += 1
#         return self.func(*args, **kwargs)

# @Decorator
def dfs(s, number_list):
    if number_list:
        if number_list[0] == s:    
            return dfs(s-number_list[0], number_list[1:]) + dfs(s, number_list[1:]) + 1
        else:
            return dfs(s-number_list[0], number_list[1:]) + dfs(s, number_list[1:])
    else:
        return 0

print(dfs(s, number_list))