[백준][Python][14225][브루트 포스] 부분수열의 합

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

14225번: 부분수열의 합

원래는 재귀 항목에 있는 문제이지만 난 그런 거 안 쓴다.

 

숫자 리스트를 받고, 이 리스트의 멱집합을 구한다. 이 부분집합들의 합을 더한 뒤 정렬한다.

코드가 최적화가 안됐다고 할 수 있는데, 어차피 멱집합은 O(2^n)이다. 정렬 한두 번 더한다고 O(nlogn)이다.

 

그 후, 0부터 돌면서 숫자 확인을 해서 이 안에 있으면 그 값을 출력하고 종료한다.

문제는 1 같은 게 있어서 모든 숫자가 가능한 경우인데, 이때는 가능한 가장 큰 값 + 1 이 답이 된다.

 

import sys
from itertools import chain, combinations


def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


n = int(sys.stdin.readline())
s = [int(i) for i in sys.stdin.readline().split()]

l = []
for c in powerset(s):
    l.append(sum(c))

l = list(set(l))
l.sort()
ret = 0
for c in l:
    if ret != c:
        print(ret)
        sys.exit()
    else:
        ret += 1
        
print(l[-1]+1)