[BOJ, 백준] 14225 - 부분수열의 합 (Python, 파이썬)

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

문제

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

 

입력

첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

예제 입출력

풀이

# 부분수열의 합 / 14225.py
# 알고리즘 분류: 브루트포스 알고리즘
import heapq
from itertools import combinations

n=int(input())
arr=list(map(int,input().split()))
heap=[]
for i in range(1,n+1):
    for x in combinations(arr,i):
        heapq.heappush(heap,sum(x))

l=len(heap)
x=0; ans=heap[-1]+1; t=0;i=1
while heap:
    x=heapq.heappop(heap)
    if t==x:
        continue
    t=x
    if i!=x:
        ans=i
        break
    i=i+1

print(ans)

 

시간 때문에 어떻게 해야할지 고민을 조금 했지만 브루트포스 알고리즘으로 풀면 되었다.

combinations를 이용해서 모든 값들을 heap에다가 넣어주도록 한다.

 

그리고 heap을 하나씩 pop해주면서 1씩 증가하는 값과 비교해주도록 한다.

만약 같지 않다면 그 값이 답이 되는 것이다.