BOJ_14225 [ 부분수열의 합 ] [ 파이썬 ]

문제

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

14225번: 부분수열의 합

문제 해결 방법

주어진 수열에서 나올 수 있는 모든 수들을 구하고 1부터 200만까지 for문을 돌면서 

만들 수 없는 수를 발견하면 출력만 해주면 된다.

소스 코드 보기

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_14225.py

jokerKwu/BOJ_Algorithm

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
answer = []

def dfs(value, index):
    if index == n:
        return 0;
    value += arr[index]
    answer.append(value)
    dfs(value, index+1)
    value -= arr[index]
    dfs(value, index+1)

dfs(0,0)
a = set(answer)
for num in range(1, 2000000):
    if num not in a:
        print(num)
        break