[코테, 알고리즘] 백준 class 5 - 중간에서 만나기 (부분수열의 합)

[1208] 부분수열의 합 2

중간에서 만나기

브루트포스의 일종으로, 문제를 절반으로 나눠서 양쪽 절반에서 모든 경우를 다 해보는 방법이다.

탐색할 때 시간복잡도를 많이 줄일 수 있다.

별 다른건 없고 그냥 똑같은 과정을 왼쪽 오른쪽 반반 나눠서 각자 수행한 다음 그 결과들을 보고 답을 내는 것이다. (딱히 재귀도 아님)

코드

import sys
input = sys.stdin.readline
from itertools import combinations
from bisect import bisect_left, bisect_right

# 부분수열의 합을 구하는 완전탐색 방식
def getSum(nums, sums):
  for i in range(1, len(nums)+1):
    for c in combinations(nums, i):
      sums.append(sum(c))
  sums.sort() # 이분탐색을 사용해야하기 때문에 정렬 필요

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

left = numbers[:N//2] # 왼쪽절반
right = numbers[N//2:] # 오른쪽절반
left_sum = [0] # left(왼쪽절반)의 부분수열의 합을 담는 곳
right_sum = [0] # right(오른쪽절반)의 부분수열의 합을 담는 곳

getSum(left, left_sum) # 왼쪽절반에서 부분수열의 합 구하기
getSum(right, right_sum) # 오른쪽절반에서 부분수열의 합 구하기

answer = 0
for l in left_sum:
  # right_sum에 S-l이 몇개 있는지는 이분탐색으로 구함
  answer += bisect_right(right_sum, S-l) - bisect_left(right_sum, S-l)

if S == 0: # 왼쪽에서 0, 오른쪽에서 0 선택했을 때 예외처리
  answer -= 1

print(answer)

• 부분수열의 합 구하기
• 이분탐색으로 타겟 개수 구하기