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

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

1208번: 부분수열의 합 2

 

문제 해결

• 정수의 최대 개수가 40개이므로 하나씩 계산을 하면 O($40^{40}$) = O(1.2089258e+64)이므로 무조건 시간초과이다.
• 하지만 연속된 부분수열의 합이 아니고 규칙이 있는 것도 아니기 때문에 하나씩 계산해야 할 수 밖에 없다.
• 그 결과 수열을 20개씩(절반씩) 잘라서 계산한 후 합이 0이 되는 개수를 더하는 방법을 생각할 수 있다.
  • 이 때 O($ 2 \times 20^{20}$) = O(2.097152e+26) 이 나오는데 만족할만한 크기는 아니여도 pypy3에서 돌아갈만하다.
• 백트래킹을 이용해서 계산한다.
• 참고로 S==0일시 계산한 answer의 값에서 1을 빼는 추가 계산해야한다.
  • 왜냐하면 처음에 각 딕셔너리에 공집합의 경우를 대비해 left[0]+=1 right[0] +=1을 해주었기 때문이다.
    • 이해가 안될 수 있는데 두 딕셔너리로 분할 했고 한쪽 딕셔너리에서만 사용하는 경우도 있을 것이다. 이 때 다른쪽은 공집합이므로 합이 0인 경우를 사용했다고 보았다. 그런데 만약 합이 0인 경우를 구하라고 하면 공집합X공집합인 경우 0인 경우도 추가 계산이 되어서 삭제해야 한다는 것이다.

 

CODE

from collections import defaultdict
def Backtracking(seq,lst,total,idx,dictionary):
    global left, right
    if dictionary == 'left_side':
        left[total] += 1
    elif dictionary == 'right_side':
        right[total] += 1
    for i in range(idx,len(lst)):
        next_lst = seq+[lst[i]]
        next_sum = total + lst[i]
        Backtracking(next_lst,lst,next_sum,i+1,dictionary)

n, s = map(int, input().split())
A = list(map(int, input().split()))
start = 0
mid = len(A)//2
end = len(A)
left = defaultdict(int)
right = defaultdict(int)
Backtracking([],A[start:mid],0,0,'left_side')
Backtracking([],A[mid:end],0,0,'right_side')
answer = 0
for l in left.keys():
    if (s-l) in right.keys():
        answer += left[l]*right[s-l]
if s ==0:
    answer -= 1
print(answer)