[BOJ/Python] 1208. 부분수열의 합2

📌 문제

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

1208번: 부분수열의 합 2

 

📌 문제 접근 방법

1. 시간 초과를 피하기 위해 리스트를 2개로 나누어 준다.
   (N의 최대값은 40으로, 나누지 않고 부분집합을 구할 경우 2^40번의 연산이 필요하다.
   둘로 나눌 경우, 2^20 + 2^20번의 연산으로 줄일 수 있다.)
2. left, right로 나눈 두 개의 부분집합에 대해서 나올 수 있는 합의 경우의 수를 구한다.
3. 투 포인터를 활용하여 각 부분집합의 합을 이용해서 S를 만들 수 있는지 확인하고 카운팅한다.
4. → 하지만 틀렸습니다!!👿
   2번에서 구한 합의 경우의 수에서 똑같은 숫자가 여러 번 있는 경우를 생각해줘야 했다.
   cnt 세는 부분을 고치니까 드디어 맞았습니다...!

 

📌 코드

from itertools import combinations
from collections import defaultdict

N, S = map(int, input().split())
numbers = list(map(int, input().split()))

mid = N//2
left = numbers[:mid]
right = numbers[mid:]

left_sum = defaultdict(int)
right_sum = defaultdict(int)

for i in range(len(left) + 1):
    for combo1 in combinations(left, i):
        left_sum[sum(combo1)] += 1

for j in range(len(right) + 1):
    for combo2 in combinations(right, j):
        right_sum[sum(combo2)] += 1

left_sum_num = sorted(left_sum.keys())
right_sum_num = sorted(right_sum.keys())

l_pointer = 0
r_pointer = len(right_sum_num) - 1
cnt = 0

while l_pointer < len(left_sum_num) and 0 <= r_pointer:
    temp = left_sum_num[l_pointer] + right_sum_num[r_pointer]

    if temp == S:
        cnt += left_sum[left_sum_num[l_pointer]] * right_sum[right_sum_num[r_pointer]]
        l_pointer += 1
        r_pointer -= 1
    elif temp > S:
        r_pointer -= 1
    else:
        l_pointer += 1

# 공집합 + 공집합인 경우 빼주기
if S == 0:
    cnt -= 1

print(cnt)