[Python/파이썬] 백준 1208번: 부분수열의 합 2

문제

 

풀이

1. 주어진 수열을 절반으로 나눈다.

 

[-7, -3, -2, 5, 8] -> [-7, -3], [-2, 5, 8]

 

2. 나눠진 수열의 부분 수열을 구한다.

 

A : [-7, -3] -> [-7], [-3], [-7, -3]

B : [-2, 5, 8] -> [-2], [5], [8], [-2, 5], [-2, 8], [5, 8], [-2, 5, 8]

 

3. A의 부분 수열 중 하나를 선택하고, B의 부분 수열 중 하나를 선택하면 모든 부분 수열을 구할 수 있다.

 

ex) [-7, -3, 5] = [-7, -3] + [5]

 

4. A, B 부분 수열의 합을 배열에 저장한다.

 

sumA : [-7, -3, -10]

sumB : [-2, 3, 5, 6, 8, 11, 13]

 

5. sumA, sumB 그리고 sumA 원소 + sumB 원소를 통해 모든 부분 수열의 합을 구할 수 있다.

 

중요한 부분은 다 설명했으니 나머지는 생략한다.

코드

import sys
from itertools import combinations
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

def getNum(arr, find):
    return bisect_right(arr, find) - bisect_left(arr, find)

def getSum(arr, sumArr):
    for i in range(1, len(arr) + 1):
        for a in combinations(arr, i):
            sumArr.append(sum(a))
    sumArr.sort()

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

left, right = arr[:n//2], arr[n//2:]
leftSum, rightSum = [], []

getSum(left, leftSum)
getSum(right, rightSum)
ans = 0
for l in leftSum:
    find = s - l
    ans += getNum(rightSum, find)

ans += getNum(leftSum, s)
ans += getNum(rightSum, s)

print(ans)

 

마무리

풀이의 3번을 생각하지 못해 구글링 해서 풀었다 ㅠㅠ