[백준 1208번] 부분 수열의 합 2

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

1208번: 부분수열의 합 2

 

 

# 조건

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

 

입력

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

 

출력

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

 

# 접근 방법

• 주어지는 최대 수의 개수가 40개이므로 2^40개의 조합을 구한다면 시간초과
• 따라서, 절반을 나누어서 2^20개씩 구해준다.
• 반으로 나누어서 왼쪽 수열과, 오른쪽 수열의 부분 수열의 합을 구해준다.
• 생성된 두개의 합 리스트를 투 포인터를 이용하여 S와 같은지 비교해준다.
• 여기서, 하나는 합이 작은 값부터 인덱싱
• 나머지 하나는 합이 큰 값 부터 인덱싱
• 주의할 점은 A + B = S가 되었을 때, A와 B가 여러 개일 수 있으므로 고려해주어야 한다
  • 왼쪽 수열에서 A와 같은 값의 개수 - c
  • 오른쪽 수열에서 B와 같은 값의 개수 - d
  • result에 c * d의 값을 추가해준다.
• S가 0인 경우 COMBINATIONS를 활용하면 공집합이 생기므로 -1을 해주어야 한다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from itertools import combinations  
  
  
N, S = map(int, input().split())  
nums = [*map(int, input().split())]  
left, right = nums[:N//2], nums[N//2:]  
  
leftSum, rightSum = [], []  
# 왼쪽의 경우 0개부터 N//2개의 부분 수열이 생길 수 있다.  
for i in range(N//2+1):  
    intermediateResults = list(combinations(left, i))  
    for j in intermediateResults:  
        leftSum.append(sum(j))  
# 오른쪽의 경우 0개부터 N-N//2개의 부분 수열이 생길 수 있다.  
for i in range(N-N//2+1):  
    intermediateResults = list(combinations(right, i))  
    for k in intermediateResults:  
        rightSum.append(sum(k))  
  
leftSum.sort()  
rightSum.sort()  
  
result = 0  
leftPoint = 0  
rightPoint = len(rightSum) - 1  
  
while leftPoint < len(leftSum) and rightPoint >= 0:  
    curSum = leftSum[leftPoint] + rightSum[rightPoint]  
    if curSum == S:  
        # 현재 값들 기록  
        leftValue = leftSum[leftPoint]  
        rightValue = rightSum[rightPoint]  
        leftPoint += 1  
        rightPoint -= 1  
        # 같은 것이 몇 개인지 알아야 되므로 기록해준다.  
        leftSame = 1  
        rightSame = 1  
        while leftPoint < len(leftSum) and leftValue == leftSum[leftPoint]:  
            leftPoint += 1  
            leftSame += 1  
        while rightPoint >= 0 and rightValue == rightSum[rightPoint]:  
            rightSame += 1  
            rightPoint -= 1  
  
        result += rightSame * leftSame  
    elif curSum < S:  
        leftPoint += 1  
    else:  
        rightPoint -= 1  
  
print(result if S != 0 else result - 1)