[백준] 14225. 부분수열의 합 - Python3

문제 설명

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 문제

• 알고리즘 분류 - Brute Force, ...
• 난이도 - 실버1

---

접근 방법

1. Brute Force

1) 부분 배열의 원소의 개수가 1~n개일 때의 모든 조합을 구하고, 그에 대한 부분합을 저장한다.

2) 부분합을 저장한 배열에 대해 중복 원소를 제거 및 정렬하고, 부분합 배열과 1~(부분합의 최댓값)의 자연수 수열을 비교하다보면 최초로 다른 값이 답이 된다.

 

(다른 분들 해답 보니까 DP로 실행시간 32ms였나 엄청 효율적으로 푸신 분도 있고, DFS로 200ms대로 푸신 분도 있어서 다른 방법도 시도해볼 예정)

---

답안 코드 1. Brute Force

메모리: 96212 KB , 시간: 472 ms, 코드 길이: 471 B

import sys
import itertools

def subsum(S):
    sums=[]
    
    # 부분합 구하기
    for cnt in range(1, len(S)+1):
        for seq in itertools.combinations(S,cnt):
            sums.append(sum(seq))
    
    sums = sorted(list(set(sums)))
    answer = max(sums)+1
    
    # 부분합으로 구할 수 없는 가장 작은 자연수 구하기
    for i in range(1, max(sums)):
        if i != sums[i-1]:
            answer = i
            break
    return answer
        

N = int(sys.stdin.readline())
S = list(map(int, sys.stdin.readline().split()))

print(subsum(S))