[BOJ] 1208 / 부분수열의 합 2 / Python 파이썬

[BOJ] 1208 / 부분수열의 합 2 / Python 파이썬

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

1208번: 부분수열의 합 2

 

 

풀이

1181 / 부분수열의 합 문제의 심화 문제이다.

 

부분수열의 합 문제의 경우에는 주어진 수열의 길이가 최대 20개 이므로 Combinations 과 DFS 로 모든 경우의 수를 구하여서 해결 하였다.

하지만 부분수열의 합 2 문제에서는 수열의 길이가 최대 40이기 때문에, 모든 경우가 2**40 개로 어마어마한 시간이 걸리게 된다.

 

이를 극복하기 위하여 수열을 절반으로 나누어 왼쪽과 오른쪽 수열을 각각 DFS 로 해결 하였다.

 

2**40 -> (2**20)* 2 = 2**21

 

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

nums = list(map(int, input().split()))

res = 0

leftNums = {}


def DFS(idx, E, add, side):
    global S, N, res
    if idx == E:
        if side == 'L':
            if not add in leftNums:
                leftNums[add] = 1
            else:
                leftNums[add] += 1
        elif S-add in leftNums:
            res += leftNums[S-add]
        return

    DFS(idx+1, E, add+nums[idx], side)
    DFS(idx+1, E, add, side)


# 왼쪽 절반 수열
DFS(0, N//2, 0, 'L')

# 오른쪽 절반 수열
DFS(N//2, N, 0, 'R')

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