문제 링크

<aside> 💡 이분 탐색/중간에서 만나기

</aside>

Memory 223068KB Time 1208ms Code Length 638B

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

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

def part_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

sub_sum1 = defaultdict(int)
sub_sum2 = defaultdict(int)

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

answer = sub_sum1[s] + sub_sum2[s]

for s1 in sub_sum1:
    if s-s1 in sub_sum2:
        answer += sub_sum1[s1] * sub_sum2[s-s1]

print(answer)

이 코드는 주어진 배열의 부분집합 중에서 합이 특정 값(s)인 부분집합의 개수를 찾는 것이다.

먼저, sys.stdin.readline을 이용해 입력을 받는다. 그리고 이를 n(배열의 길이)과 s(찾고자 하는 합)로 분리한다.

입력받은 배열을 반으로 나누어 각각의 부분집합의 합을 구하고, 이를 딕셔너리에 저장한다. 이때 딕셔너리의 키는 부분집합의 합이고, 값은 그 합을 가지는 부분집합의 개수이다.

그 후, 두 딕셔너리에서 s를 찾아 그 개수를 더하고, 두 딕셔너리의 합이 s가 되는 경우를 찾아 그 개수를 더한다.

마지막으로, 이렇게 구한 부분집합의 개수를 출력한다.