백준 1208

www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

문제

---

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

 

 

입력

---

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

출력

---

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

 

접근법은 음... 처음에는 부분수열의 문제 합 처럼 풀려했는데 그 가짓수가 (2^40)가짓수가 되기 때문에 어떻게 풀지 고민하였다,,, 이런 간단한 류의 문제들이 더욱 고민하게 만든다.

결국 해결법은

1. 주어진 리스트를 받아서 2개의 집합으로 나누어준뒤,
2. 2개의 리스트 의 collections 툴을 이용하여, 부분집합의 합들을 모두 구해준다. <list_1+=list(sum(k) for k in combinations(num,i) 부분>
3. 그 다음, 부분집합들을 정렬해주고(sort)
4. 부분집합들의 처음과 끝에 포인터를 설정한 후, 포인터 들의 합이 m이 될때마다 count 해준다.
5. <단! 여기서 주의해야 할 점은 list_1[left]+list_2[right] == m 일때, list_1[left]와 list_1[left+1]이 같을 때, 또는 list_2[right]와 list_2[right-1]이 같을때, 처리를 해주는 것을 유의해서 보자.>

from itertools import combinations
n,m = map(int,input().split())
num = list(map(int,input().split()))

# 부분수열의 합 문제 이기에 가장 먼저 부분수열들의 합을 구해준다.
# 여기서 문제는 주어진 숫자 n이 너무 크기 때문에 (2^40-1) 
# num을 절반으로 나누고 부분수열의 합들을 일렬로 정렬 후 답을 구해준다.

num1 = num[:len(num)//2]
num2 = num[len(num)//2:]
list_1=[]
list_2=[]

for i in range(0,len(num1)+1):
    list_1 += list(sum(k) for k in combinations(num1,i))
    list_1.sort()

for i in range(0,len(num2)+1):
    list_2 += list(sum(k) for k in combinations(num2,i))
    list_2.sort()    


# 각 리스트에 대해 2개의 포인터 즉 , list_1에는 left, list_2에는 right을
# 잡아서 부분수열의 합을 구해준다.<list_1과 list_2에는 같은 부분집합이 
# 존재 할 수 없으므로 더해도 상관이 없다.>
left = 0
right = len(list_2)-1
cnt = 0
while left<len(list_1) and right>=0:
    temp = list_1[left] + list_2[right] 
    # list_1[left] + list_2[right] ==m 이라면 left-=1 right+=1
    if temp == m:
        temp1=1
        temp2=1
        left+=1
        right-=1
        # 이 부분은 부분수열 중에서 left-=1 또는 right+=1을 하여도 
        # list[] 값이 변하지 않는 부분을 통째로 곱해서 더해주는 부분이다..
        # 처음 이 부분을 고려하지 않아 재채점 받았다..
        while left<len(list_1) and list_1[left]==list_1[left-1]:
            temp1+=1
            left+=1
        while right>=0 and list_2[right] == list_2[right+1]:
            temp2+=1
            right-=1
        cnt+=temp1*temp2
    elif temp < m: # m보다 작기 때문에 left+1
        if left+1<len(list_1): left+=1
        else: break
    else:
        if right-1>=0: right-=1
        else: break
if m == 0: cnt-=1
print(cnt)