BaekJoon 14225 - 부분수열의 합 (Python)

바로 직전에 풀어보았던 GCD 합 문제처럼 combinations library를 이용하면 쉽게 풀 수 있는 문제였다.

 

from itertools import combinations    # 수학에서의 조합을 사용할 수 있게 해주는 library
import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

result = []    # 정답 저장

N = int(input())    # 수열 S의 크기
S = list(map(int, input().strip().split(' ')))    # 수열 S

for i in range(1, N+1):    # 수열 S의 크기만큼 반복
    for args in list(combinations(S, i)):    # 수열 S에서 i개를 꺼내어 조합
        result.append(sum(args))    # 조합으로 나온 수 i개를 합하여 나온 결과를 저장

result = set(sorted(result))    # 중복 제거를 위해 집합으로 변환

for i in range(1, max(result) + 2):    # 1부터 result의 결과보다 1 큰 수까지 반복
    if i not in result:    # 정수 i가 result에 존재하지 않을 경우 출력 후 마침
        print(i)
        break

 

combinations의 수학적 정의를 생각해보면, nCx에서 x가 n/2를 넘어가면 n-x로 바뀌는 경우 시간이 더 적게 소모된다.

 

해당 부분을 적용하면 시간적인 부분에서 더 감소하지 않을까 생각하여 다시 제출하였다.

 

from itertools import combinations    # 수학에서의 조합을 사용할 수 있게 해주는 library
import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

result = []    # 정답 저장

N = int(input())    # 수열 S의 크기
S = list(map(int, input().strip().split(' ')))    # 수열 S

for i in range(1, N+1):    # 수열 S의 크기만큼 반복
    if i > N/2:    # 현재 정수가 N/2보다 크다면
        for args in list(combinations(S, N-i)):    # 수열 S에서 N-i개를 꺼내어 조합
            result.append(sum(S) - sum(args))    # 조합으로 나온 수 i개를 합하여 나온 결과를 전체 수열의 합에 뺀 후 저장
    else:    # 현재 정수가 N/2보다 작다면
        for args in list(combinations(S, i)):    # 수열 S에서 i개를 꺼내어 조합
            result.append(sum(args))    # 조합으로 나온 수 i개를 합하여 나온 결과를 저장

result = set(sorted(result))    # 중복 제거를 위해 집합으로 변환

for i in range(1, max(result) + 2):    # 1부터 result의 결과보다 1 큰 수까지 반복
    if i not in result:    # 정수 i가 result에 존재하지 않을 경우 출력 후 마침
        print(i)
        break