백준 1208번 부분수열의 합 2 (Python 3)

 

Baekjoon online judge 1208번 파이썬

 

링크

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

1208번: 부분수열의 합 2

시간을 줄이기 위해 반으로 나누는게 핵심

만약 나누지 않고 모든 경우를 구한다고 생각하면, n이 40이면, 부분 수열은 2^40으로 약 1조가 되기때문에 불가능하다.

반면, 반으로 나누어서 부분 수열을 구하면, 2*2^20으로 약 2백만 정도로 줄일 수 있다.

이제 반으로 나눈 부분 수열에 대해서 합을 구하고, 그 합 중에서 찾고자 하는 값을 찾으면 된다.

왼쪽 부분 수열에 찾고자 하는 값이 있는 경우의 수 + 오른쪽 부분 수열에 찾고자 하는 값이 있는 경우의 수 +

왼쪽 부분 수열과 오른쪽 부분 수열의 합이 찾고자 하는 값인 경우의수를 구하면 된다.

 

소스코드

import sys
import bisect
from itertools import combinations
input=sys.stdin.readline

def find(arr,num):
    return bisect.bisect_right(arr,num)-bisect.bisect_left(arr,num)


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

left=seq[:n//2]
right=seq[n//2:]

sumleft=[]
sumright=[]

for i in range(1,len(left)+1):
    possible=combinations(left,i)
    for p in possible:
        sumleft.append(sum(p))

for i in range(1,len(right)+1):
    possible=combinations(right,i)
    for p in possible:
        sumright.append(sum(p))

sumleft.sort()
sumright.sort()
ans=0
#sumleft만으로 s가 되는경우
ans+=find(sumleft,s)
#sumright만으로 s가 되는경우
ans+=find(sumright,s)
#sumleft+sumright인 경우
for k in sumleft:
    ans+=find(sumright,s-k)

print(ans)