[백준] 부분수열의 합 (14225번) - Python

문제

https://www.acmicpc.net/problem/14225

아이디어

• combinations 라이브러리를 이용하여 수열에서 숫자 고르기
  • 수열 전체 길이 / 2 까지만 고름
  • 굳이 모든 경우의 수를 구할 필요가 없다!
    전체 합에서 고른 수들의 합을 빼면 나머지 반도 구할 수 있다!
    (n개의 수 중 a개 만큼 뽑을 때, n개 전체 합 - a개 합 == n-a개 합)
• 자연수 탐색을 빠르게 하기 위해 set에 저장

코드

from itertools import combinations

n = int(input())
s = list(map(int, input().split()))

total = sum(s)

nums = set(s)
nums.add(total)

# 수열 길이 / 2 개 까지만 경우의 수 구함
for count in range(1, n//2+1):
    for combi in combinations(s, count):
        num = sum(combi)    # count개 합
        nums.update((num, total-num))   # count 합, n-count 합

# 제일 작은 자연수 탐색
answer = 1
while answer in nums:
    answer += 1

print(answer)

개선점

• 수열 길이에 따라 중복된 합이 나오게 된다 (set에 저장했기 때문에 큰 문제는 X)