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

문제:www.acmicpc.net/problem/14225

14225번: 부분수열의 합

 

import sys
input=sys.stdin.readline
N=int(input())
li=list(map(int,input().rstrip().split()))
visited=[False]*N
li.sort()
sumList=[]
maxNum=2000000
numList=[False]*(maxNum)
numList[0]=True
def func(ceil,aim,sum,ans):
    if ceil==aim:
        return
    for i in range(len(li)):
        if not ans:
            visited[i]=True
            sum+=li[i]
            numList[sum]=True
            ans.append(i)
            func(ceil+1,aim,sum,ans)
            ans.pop()
            sum-=li[i]
            visited[i]=False
        elif not visited[i] and ans[-1]<i:
            visited[i]=True
            sum+=li[i]
            ans.append(i)
            numList[sum]=True
            func(ceil+1,aim,sum,ans)
            ans.pop()
            sum-=li[i]
            visited[i]=False
        
func(0,len(li),0,[])
cnt=1
while True:
    if numList[cnt]==False:
        print(cnt)
        break
    else:
        cnt+=1

윗 부분은 내가 작성한 코드다. 풀이방법은 모든 수열을 만들면서 조사하는 형식으로 했다. 그러면서 가능한 수들은 리스트에서 True로 설정하고 1부터 반복문을 돌면서 for문에서 False를 만나면 답을 출력하는 형식으로 작성하였다.

근데 이 코드의 단점은 시간복잡도가 꽤 큰 편에 속한 것이 문제였다. 

그래서 다른 사람의 코드를 참고해봤다.

 

n = int(input())
a = list(map(int,input().split()))
c = [False]*(n*100000+10)
def go(i, sum):
    if i == n:
        c[sum] = True
        return
    go(i+1,sum+a[i])
    go(i+1,sum)
go(0,0)
i = 1
while True:
    if c[i] == False:
        break
    i += 1
print(i)

윗 코드를 설명해보자면 이제 각각의 수는 포함되는 경우와 포함되지 않는 경우 두가지 경우가 있는데 이를 코드로 표현하면 go함수와 같다.

그리고 다음 반복문은 내 코드와 같다.