문제
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)
