[python]백준 1208번 - 부분수열의 합 2

1208번: 부분수열의 합 2 (acmicpc.net)

1208번: 부분수열의 합 2

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

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

left, right = arr[:n//2], arr[n//2:]
tmpleft, tmpright = [], []

for i in range(1, len(left)+1):
    tmp = itertools.combinations(left, i)
    for j in tmp:
        tmpleft.append(sum(j))
tmpleft.sort()

for i in range(1, len(right)+1):
    tmp = itertools.combinations(right, i)
    for j in tmp:
        tmpright.append(sum(j))
tmpright.sort()

ans = 0
for i in tmpleft:
    t = s - i
    ans += bisect.bisect_right(tmpright, t) - bisect.bisect_left(tmpright, t)

ans += bisect.bisect_right(tmpright, s) - bisect.bisect_left(tmpright, s)
ans += bisect.bisect_right(tmpleft, s) - bisect.bisect_left(tmpleft, s)
print(ans)

---

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

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

tmp = []
for i in range(1,n+1):
    c = itertools.combinations(arr, i)
    for j in c:
        tmp.append(sum(j))

tmp.sort()
ans = bisect.bisect_right(tmp, s) - bisect.bisect_left(tmp, s)

print(ans)

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

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

tmp = []
for i in range(1,n+1):
    c = itertools.combinations(arr, i)
    for j in c:
        temp = sum(j)
        if temp == s:
            tmp.append(temp)


print(len(tmp))

처음에 접근을 진짜 단순하게 했는데

이렇게 되면 조합이 진짜 커져서 메모리 초과랑 시간 초과 나오더라구요

 

부분수열을 크게 둘로 나눠서

앞에서만 나올 경우

뒤에서만 나올 경우

앞,뒤 합쳐서 나올 경우로 해서 (구글링해서) 풀었습니다