백준 14225 파이썬 - 부분수열의 합

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

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이다.

코드

import sys
n = int(sys.stdin.readline())
s = list(map(int, sys.stdin.readline().split()))
arr = [0] * 10000000
def dfs(i, a):
    if i == n:
        return
    a += s[i]
    arr[a] = 1
    dfs(i + 1, a)
    dfs(i + 1, a - s[i])
dfs(0, 0)
for i in arr:
    if i == 0:
        print(arr[1:].index(i) + 1)
        break

풀이

dfs로 s리스트의 원소들을 더한 값들과 뺀 값들이 존재하면 arr배열의 값을 0이 아닌 1로 바꿔주고 arr배열에서 인덱스가 0이 아닌 수들 중 1이 아닌 가장 작은 수를 찾아 출력한다.