[알고리즘/백준] 14225번 : 부분수열의 합(python)

여러가지 방법이 있다.

처음에는 combinations를 사용하여 풀었다.

import sys
from itertools import combinations


input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
a.sort()
ans = set([i for i in range(1, N*max(a) + 2)])
for i in range(1, N+1):
    for j in combinations(a, i):
        if sum(j) in ans:
            ans.discard(sum(j))
print(min(ans))

두번째 풀이는 1씩 증가하면서 다음 수가 더 크면 현재 수가 가장 작은 수..

import sys


input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(N):
    if i == 0:
        if a[i] == 1:
            continue
        else:
            print(1)
            break
    if sum(a[:i]) + 1 < a[i]:
        print(sum(a[:i]) + 1)
        break
else:
    print(sum(a, 1))