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

14225번: 부분수열의 합

 

처음 푼 코드

from itertools import combinations


N = int(input())
arr = list(map(int, input().split()))
max_value = sum(arr)

num_set = set()
for n in range(1, N+1):
    for c in combinations(arr, n):
        num_set.add(sum(c))

i = 1
while True:
    if i not in num_set:
        print(i)
        exit()
    i += 1

 

브루트포스틱 하게 풀어서 굉장히 지저분하다. 내가 면접관이면 이렇게 푼 사람 안뽑을 것 같아서 다른 방법으로 풀어봤다.

 

다시 푼 코드

N = int(input())
arr = sorted(list(map(int, input().split())))
answer = 0
for i in arr:
    if answer + 1 < i:
        break
    answer += i
print(answer + 1)

쏘 머취 better

1. 우선 입력받은 수열을 오름차순으로 정렬

2. 정렬된 수를 순회

3. answer + 1 이 순회하는 값 보다 작다는 건, answer + 1 이 답이라는 의미. 

4. 그렇지 않을 경우엔 answer 에 현재 순회중인 값 i 를 더한다. 이는 현재 i 값 보다는 큰 수가 정답이 될 것이란 의미.

5. for 문을 빠져나올 때의 answer + 1 값이 답이 된다.