[백준] 부분수열의 합 2 (1208번) - Python

문제

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

아이디어

https://ku-hug.tistory.com/190
위 블로그 아이디어 참고

• 수열을 반으로 나누고 합이 정수 S가 되는 부분수열을 구한다.
  • 왼쪽에서 나오는 경우의 수
  • 오른쪽에서 나오는 경우의 수
  • 왼쪽과 오른쪽에서 각각 하나씩 골랐을 때 나오는 경우의 수
    
    
• 나는 defaultdict를 이용해서 특정 합이 나오는 경우의 수를 저장했는데,
  위 블로그에서는 bisect 라이브러리(이분탐색)를 활용해서 경우의 수를 셌다.
  이런 방법도 있다니..! 신기..!

코드

from sys import stdin
from itertools import combinations
from collections import defaultdict

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


# 부분수열 합 구하기
def get_sub_sum(arr:list, result:defaultdict):
    for count in range(1, len(arr)+1):
        for combi in combinations(arr, count):
            c_sum = sum(combi)
            result[c_sum] += 1


# defaultdict를 이용해서 특정 합이 나오는 경우의 수 count
sub_sum1 = defaultdict(int)
sub_sum2 = defaultdict(int)

get_sub_sum(arr[n//2:], sub_sum1)
get_sub_sum(arr[:n//2], sub_sum2)

# 각 부분 수열에 S가 있는 경우 구하기
answer = sub_sum1[s] + sub_sum2[s]


# 두 부분수열을 더해서 S가 나오는 경우의 수 구하기
for s1 in sub_sum1:
    if s-s1 in sub_sum2:
        answer += sub_sum1[s1] * sub_sum2[s-s1]


print(answer)