[🥈2 / 백준 1182 / 파이썬] 부분수열의 합

 

1182번: 부분수열의 합

 

문제

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

입력

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

출력

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

 

예제 입력  5 0 -7 -3 -2 5 8

예제 출력  1

 

풀이

 

브루트 포스(완전 탐색) 알고리즘을 이용해 부분 수열의 합이 s가 되는 경우의 수를 구하는 문제이다.

 

재귀로 탐색을 하며 인덱스 순서대로 값을 넘겨주는데, 값을 넘기는 경우와 넘기지 않는 경우로 나눈다.

즉, 예제대로 -7 -3 -2 5 8 이라면 총합에 -7 혹은 0 을 더하고 다음 인덱스인 -3으로 넘겨주고, 총합에 다시 -3 혹은 0을 더하고 다음 인덱스로 넘기는 방식이다.

 

만약 s가 0이라면 부분 수열의 크기가 0일 때에도 한 가지 경우로 더해질 것이니 이 경우에만 카운트에서 -1을 한다.

 

import sys
input = sys.stdin.readline

n,s = map(int,input().split())
nums = list(map(int,input().split()))
cnt = 0

def bf(arr,idx,summ):
    global cnt
    if idx == n:
        if summ==s:
            cnt += 1
        return
    
    bf(arr,idx+1,summ+arr[idx])
    bf(arr,idx+1,summ)
bf(nums,0,0)
print(cnt-1 if not s else cnt)

 

혹은 itertools 모듈의 combinations를 이용하여 모든 조합을 구한 뒤 각각의 합이 s가 되는 경우를 세어 문제를 해결할 수도 있다.

하지만 이 경우 문제를 간단하게 해결할 수는 있지만, 값을 바로 더해주는 것이 아니라 조합을 생성한 뒤 다시 sum을 해야 하므로 시간복잡도가 조금 증가하게 된다.

 

import sys, itertools as it
input = sys.stdin.readline

n,s = map(int,input().split())
nums = list(map(int,input().split()))
cnt = 0

for i in range(1,n+1):
    for j in list(it.combinations(nums,i)):
        if sum(j)==s:
            cnt+=1
print(cnt)