📚 1208 - 부분수열의 합 2

부분수열의 합 2

이해

N이 40개 이므로 모든 부분 수열을 다 구하려면 2^40번의 연산이 필요하다. (이는 1초안에 풀 수 없다.)

수열의 길이가 40일 때, 왼쪽 오른쪽을 나눈다면(이분 탐색)
왼쪽 : 20, 시간복잡도O(2^20)
오른쪽 : 20, 시간복잡도O(2^20)

이므로 시간은 충분하다.

• left부분 수열의 합을 sum 값이 몇 번 나왔는지 딕셔너리를 통해 저장한다. (만약 첫 입력 값이면 0 + 1이 된다.)

• right부분 idx가 n에 도착했을 떄, 딕셔너리에 S-현재 총합이 존재한다면 ans에 딕셔너리 해당 키에 대한 값을 더해준다.
  (만약 입력된 값에 결과가 0이면 0을 더한다.)

설명 잘되어 있는 곳 추가로 궁금한게 있으면 이를 참고하면 될 것 같다.

소스

import sys

read = sys.stdin.readline
n, s = map(int, read().split())

arr = list(map(int, read().split()))

dist = dict()
ans = 0


def leftSeq(idx, cur_sum):
    if idx == n//2:
        dist[cur_sum] = dist.get(cur_sum, 0) + 1
        return

    leftSeq(idx + 1, cur_sum)
    leftSeq(idx + 1, cur_sum + arr[idx])


def rightSeq(idx, cur_sum):
    global ans

    if idx == n:
        ans += dist.get(s - cur_sum, 0)
        return

    rightSeq(idx + 1, cur_sum)
    rightSeq(idx + 1, cur_sum + arr[idx])


leftSeq(0, 0)
rightSeq(n // 2, 0)

if not s:
    ans -= 1
print(ans)

참고 : https://hyeo-noo.tistory.com/128