백준 - 부분수열의 합 2 (1208)

처음 더한다, 더하지 않는다 두 가지 경우의 수로 재귀 함수를 돌렸으나

시간초과 문제로 다른 방법을 모색하게 된다.

 

1. 수열을 반으로 자른다.

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

 

2. 부분수열을 구하고 정렬한다.

[-10, -7, -3]      [-2, 3, 5, 6, 8, 11, 13]

 

3. 이분탐색으로 데이터를 하나씩 찾아준다.

bisect을 이용해서 right - left를 하면 중복 요소개수까지 구할 수 있다.

 

4. 자기 자신도 탐색을 진행한다.

 

from itertools import combinations
from bisect import bisect_left, bisect_right
def find_idx(list_data, data):
    return bisect_right(list_data, data) - bisect_left(list_data, data) # 중복 요소까지 계산

n,m = map(int, input().split())
data = list(map(int, input().split()))

ldata = data[:n//2]
rdata = data[n//2:]
l_sum_list = []
r_sum_list = []

for i in range(len(ldata)+1):
    for com in combinations(ldata,i):
        l_sum_list.append(sum(com))

for i in range(len(rdata)+1):
    for com in combinations(rdata,i):
        r_sum_list.append(sum(com))

l_sum_list = sorted(l_sum_list[1:])
r_sum_list = sorted(r_sum_list[1:])
answer = 0
for i in l_sum_list:
    answer += find_idx(r_sum_list,m-i)
answer += find_idx(l_sum_list,m)
answer += find_idx(r_sum_list,m)
print(answer)