1208. 부분수열의 합 2

업데이트 시간 : 2023-07-09 08:11:26 +0000

[Gold I] 부분수열의 합 2 - 1208

문제 링크

성능 요약

메모리: 236164 KB, 시간: 3564 ms

분류

이분 탐색, 중간에서 만나기

문제 설명

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

💡 Solutions

📄 부분수열의 합 2.py

LEFT_DICT = dict()
RIGHT_DICT = dict()


# seq: 부분수열, lst: 원본 리스트, sum_v: 누적합, idx: 현재 인덱스, option: left | right
def Backtracking(seq, lst, sum_v, idx, option):
    if option == 'LEFT':
        if sum_v in LEFT_DICT.keys():
            LEFT_DICT[sum_v] += 1
        else:
            LEFT_DICT[sum_v] = 1
    elif option == 'RIGHT':
        if sum_v in RIGHT_DICT.keys():
            RIGHT_DICT[sum_v] += 1
        else:
            RIGHT_DICT[sum_v] = 1

    for i in range(idx, len(lst)):
        next_lst = seq + [lst[i]]
        next_sum = sum_v + lst[i]
        Backtracking(next_lst, lst, next_sum, i+1, option)
        next_lst.pop()


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

start = 0
mid = len(arr)//2
end = len(arr)

Backtracking([], arr[start:mid], 0,  0, 'LEFT')
Backtracking([], arr[mid:end], 0, 0, 'RIGHT')

count = 0
for left in LEFT_DICT.keys():
    if (S - left) in RIGHT_DICT.keys():
        count += LEFT_DICT[left] * RIGHT_DICT[(S - left)]

if S == 0:
    count -= 1
print(count)