[실버2]백준 1182번(부분수열의 합) - 코테공부 26일차(2025.02.17)

문제유형

조합 알고리즘

풀이 방법 도출 과정

1. 부분수열은 주어진 원소 중 일부를 선택하는 조합과 동일한 개념 이기에 조합을 사용해보도록 하겠다. 

2. 조합을 사용하여 모든 수를 만들고 그 다음에 값들을 더한다음 첫째 줄에 합이 S가 되는 수를 찾는다.

시간 복잡도

최악의 경우 N이 20이기 떄문에 20 X 2^20= 2천만 정도 된다. O(N 2^N)

코드 및 간단설명

조합을 사용하여 풀었더니 시간초과가 나지 않았다. 

from itertools import combinations

N, S = map(int, input().split())
lst = list(map(int, input().split()))
ans = 0

for i in range(1, N + 1):
  for num in combinations(lst, i):
      print(num)
      if sum(num) == S:
          ans += 1

print(ans)

다른 풀이

1) Meet-in-the-Middle 알고리즘 사용

원래 문제는 N개의 원소에 대해 모든 부분집합을 고려하여 합이 S가 되는 경우의 수를 세는 문제인데 전체 2^N개의 부분집합을 직접 탐색하는 대신, 리스트를 두 부분으로 나누어 각 부분의 모든 부분합을 구한 후, 두 부분의 결과를 합쳐 S를 만드는 경우의 수를 계산하는 방식을 사용하였다. 

from itertools import combinations
import bisect

def get_sub_sums(arr):
    n = len(arr)
    sub_sums = []
    for i in range(n + 1):
        for comb in combinations(arr, i):
            sub_sums.append(sum(comb))
    return sub_sums

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

# 리스트를 두 부분으로 나누기
mid = N // 2
left, right = lst[:mid], lst[mid:]

# 각 부분의 부분합 구하기
sum_left = get_sub_sums(left)
sum_right = get_sub_sums(right)

# sum_right 정렬
sum_right.sort()

ans = 0
for s in sum_left:
    # S - s가 sum_right에서 등장하는 횟수 찾기
    low = bisect.bisect_left(sum_right, S - s)
    high = bisect.bisect_right(sum_right, S - s)
    ans += (high - low)

# 공집합 제외 (문제에 따라 필요)
if S == 0:
    ans -= 1

print(ans)

 

[알고리즘 기법] Meet In The Middle