[BOJ] (BF) 14225번 부분수열의 합

별다른 해법이 떠오르지 않아 처음부터 브루트포스로 접근했다.

그런데 시간초과가 났다.

아래는 시간초과가 난 코드이다.

from itertools import combinations

n = int(input())
data = list(map(int, input().split()))
arr = []

for i in range(1, n+1):
    for c in combinations(data, i):
        _sum = sum(c)
        arr.append(_sum)
    
i = 1
while True:
    if i not in arr:
        break
    i += 1

print(i)

여기서 쓸데없이 시간을 지체했던 부분은,

마지막 while 문에, if i not in arr: 를 실행할때마다 O(n)의 시간복잡도를 가진다는 것.

 

코드를 아래와 같이 수정하면 O(1)에 가능하다.

정답 코드:

from itertools import combinations

n = int(input())
data = list(map(int, input().split()))
arr = [False for _ in range(2000000)]

for i in range(1, n+1):
    for c in combinations(data, i):
        _sum = sum(c)
        arr[_sum] = True
        
for i in range(1, len(arr)):
    if not arr[i]:
        print(i)
        break