[백준(BOJ)] #1182- 부분수열의 합 (파이썬, PyPy3)

문제

 

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

---

문제 풀이

n개의 정수에서 가능한 모든 부분 수열을 구한 뒤(*Brute Force) 부분 수열의 합이 s가 되는 경우를 찾아 더해주면 됩니다.

 

Brute Force 알고리즘: Brute(무식한) + Force(힘) 무식하게 모든 경우의 수를 탐색하는 방법으로 완전 탐색을 의미함.

 

n개의 정수 -7, -3, -2, 5, 8

s = 0

 

크기가 1인 부분 수열

 

(-7), (-3), (-2), (5), (8)

 

크기가 2인 부분 수열

(-7, -3), (-7, -2), (-7, 5), (-7, 8), (-3, -2), (-3, 5), (-3, 8), (-2, 5), (-2, 8), (5, 8)

 

크기가 3인 부분 수열

(-7, -3, -2), (-7, -3, 5), (-7, -3, 8), (-7, -2, 5), (-7, -2, 8), (-7, 5, 8), (-3, -2, 5), (-3, -2, 8), (-3, 5, 8), (-2, 5, 8)

((-3, -2, 5)에서 부분 수열의 합이 s가 됨)

 

크기가 4인 부분 수열 

(-7, -3, -2, 5), (-7, -3, -2, 8), (-7, -3, 5, 8), (-7, -2, 5, 8), (-3, -2, 5, 8)

 

크기가 5인 부분 수열

(-7, -3, -2, 5, 8)

 

따라서 답은 1

 

부분 수열은 조합 공식 nCr으로 구할 수 있고, 파이썬에서는 itertools라이브러리에서 combinations함수를 제공하기 때문에 이 함수를 사용하여 풀었습니다.

 

---

구현

코드

import sys
from itertools import combinations
input = sys.stdin.readline

if __name__ == "__main__":
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    
    res = 0
    
    for i in range(1, n+1):
        for com in combinations(a, i):
            if sum(com) == s:
                res += 1
                
    print(res)

결과