[Brute Force] 백준 1182. 부분수열의 합 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1182번: 부분수열의 합

 

 

 

2. 문제 풀이

 N개의 정수에서 뽑은 부분 수열의 합이 S가 되는 경우의 수를 구하는 문제입니다. 모든 경우의 수를 시험해봐야 하므로, 브루트 포스문제입니다.

 

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 S보다 큰 정수는 경우의 수에서 배제할 수 있을지 않을까? 라고 생각할 수도 있습니다. 하지만, N개의 정수에는 음수도 포함됩니다. 따라서 배제 없이, 모든 경우의 수를 '조합'으로 구해야 합니다.

 

 

 

 

3. 코드

from itertools import combinations

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

for i in range(n):
    subarr = combinations(arr, i+1)
    for j in subarr:
        if sum(j) == s:
            cnt += 1
print(cnt)

 조합(Combination)을 사용하여 모든 경우의 수를 구합니다. itertools 라이브러리를 이용합니다.

 

 

itertools.combinations(lst, n): lst 리스트에서 n개를 뽑는 조합

 1부터 n개를 뽑는 모든 조합을 구하고, 합이 S인지 판별합니다.