[BOJ][⚪2][백준#01182] 부분수열의 합

문제 출처

BAEKJOON Online Judge #1182

문제

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

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20,

S

≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

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

예제

입력

5 0
-7 -3 -2 5 8

출력

1

My Sol

from itertools import combinations

N, S = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0
for i in range(1, N+1):
    for comb in combinations(arr, i):
        if sum(comb)==S:
            cnt += 1

print(cnt)

itertool의 조합함수 combination을 이용해 1개부터 N개까지의 원소의 집합에서 모두를 더한 값이 S라면 cnt를 1 늘리게 해주었다. 라이브러리를 사용했지만 생각보다 연산시간이 빨라서 놀랐다.

결과

맞았습니다!!

모범답안

출처

def dfs(start,s):
    global count
    if start == N:
        return

    s += arr[start]

    if s == S:
        count += 1

    dfs(start + 1,s)
    dfs(start + 1,s - arr[start])

N, S = map(int,input().split())
arr = [int(x) for x in input().split()]

count = 0
dfs(0, 0)
print(count)

비슷한 연산시간이지만, 내가 처음에 시도했던 방식으로 푸신 분이 있어서 분석해보려 한다. 트리를 이용해 각 깊이에 해당하는 인덱스에 대해서 합을 인자로 전달해주며, 해당 인덱스를 더했을 때 S와 같다면 count를 1 늘려준다.

나는 인자로 넣어주었던 ssum 값을 먼저 판별하고 그 뒤에 트리를 나누었는데, 이렇게 인덱스로 먼저 ssum에 더해주고 S와 비교하여 카운트를 올린 뒤, 다시 빼는 방식도 좋은 것 같다. 이렇게 되면 부분집합에서 최소 하나의 원소는 가지게 되는 꼴이다.