문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
예제 입력 1
5 0
-7 -3 -2 5 8
예제 출력 1
1
이걸 어떻게 하지..? 고민하다가 결국 알고리즘 분류를 봤다.
중간에서 만나기 (Meet in Middle) 알고리즘이다... 솔직히 처음 봤다.
-> 일단 어떻게 구현하는지 공부하기 후 1시간은 고민해보기
-> 문제를두 개의 작은 부분 문제로 나눔근데도 안풀려서 다른 사람의 코드를 참고함..!
(알고리즘 잘하고싶어..)
코드의 작동 !
입력받은 수열을 두 부분으로 나눕니다.
각 부분에서 가능한 모든 부분수열의 합을 구하고, 이때 나온 합을 key로 하고, 그 합을 가지는 부분수열의 수를 value로 하는 딕셔너리 sum1과 sum2를 생성합니다.
이후, sum1의 모든 key에 대해, 그 key와 더했을 때 s가 되는 key가 sum2에 존재하는지 확인합니다. 이때 존재한다면, sum1에서 그 key를 가진 부분수열의 수와 sum2에서 s에서 그 key를 뺀 값을 key로 가진 부분수열의 수를 곱한 값을 결과에 더합니다.
마지막으로, s가 0인 경우 sum1과 sum2에서 key가 0인 부분수열의 수를 더해주되, 이때는 전체 수열이 아무것도 선택되지 않는 경우를 1번만 세야하므로 -1을 해줍니다. s가 0이 아닌 경우에는 그냥 sum1과 sum2에서 key가 s인 부분수열의 수를 더해줍니다.
위의 과정을 거치면 s가 되는 부분수열의 총 개수를 구할 수 있습니다.
코드
from collections import defaultdict
from itertools import combinations
def subsequence_sum_2():
# 숫자의 개수(N)와 목표 합(S)을 입력 받음
N, S = map(int, input().split())
# 숫자들을 리스트로 입력 받음
nums = list(map(int, input().split()))
# 만약 숫자가 하나뿐이라면, 그 숫자가 목표 합과 같은지 검사한 후 결과를 반환
if N == 1:
return 1 if nums[0] == S else 0
# 숫자 리스트를 반으로 나눔
mid = N // 2
nums1, nums2 = nums[:mid], nums[mid:]
# 각 부분 리스트에서 가능한 합의 개수를 저장할 딕셔너리를 준비
sums1, sums2 = defaultdict(int), defaultdict(int)
# 첫 번째 부분 리스트에서 가능한 모든 합을 구함
for i in range(1, mid + 1):
for comb in combinations(nums1, i):
sums1[sum(comb)] += 1
# 두 번째 부분 리스트에서 가능한 모든 합을 구함
for i in range(1, N - mid + 1):
for comb in combinations(nums2, i):
sums2[sum(comb)] += 1
# 첫 번째와 두 번째 부분 리스트에서 각각 합이 S가 되는 경우의 수를 더함
result = sums1[S] + sums2[S]
# 첫 번째 부분 리스트의 합과 두 번째 부분 리스트의 합이 합쳐서 S가 되는 경우의 수를 더함
for sum1 in sums1:
if S - sum1 in sums2:
result += sums1[sum1] * sums2[S - sum1]
# 결과 반환
return result
print(subsequence_sum_2())
