[실버 1] 백준 14225 - 부분수열의 합 (파이썬)

 

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

 

풀이

itertools.combinations를 이용해서 길이 1부터 N까지 모든 조합을 구한다.

각 조합의 합을 리스트 sums에 추가한다.

sums = []
for i in range(1, N + 1):
    for combination in combinations(S, i):
        sums.append(sum(combination))

중복된 합들을 제거한 후, 오름차순으로 정렬한다.

sums = list(set(sums))
sums.sort()

그 후 만들 수 없는 가장 작은 자연수를 찾기 위해서

answer = len(sums) + 1
for i in range(len(sums)):
    if sums[i] != i + 1:
        answer = i + 1
        break

자연수는 1부터 시작하므로, i + 1이 각 합과 일치하는지 확인한다.

sums[i] ≠ i + 1이면, 그 수는 만들 수 없는 가장 작은 자연수이다.

만약 모든 수가 다 맞아떨어지면, 마지막 수보다 1더 큰 수를 출력한다.

코드

# 백준 14225 - 부분수열의 합
# 분류 : 브루트포스
 
from itertools import combinations
 
N = int(input())
S = list(map(int, input().split()))
 
sums = []
for i in range(1, N + 1) :
    for combination in combinations(S, i) :
        sums.append(sum(combination))
 
sums = list(set(sums))
sums.sort()
 
answer = len(sums) + 1
for i in range(len(sums)) :
    if sums[i] != i + 1 :
        answer = i + 1
        break
    
print(answer)