백준 14225 - 부분수열의 합

문제 

14225번: 부분수열의 합

LIS알고리즘 설명 / 출처: https://chanhuiseok.github.io/posts/algo-49

접근 

- 입력된 수열을 정렬한 후에 순서대로 처리

- 변수 a는 현재까지의 부분합

- 반복문을 통해 수열을 순회하면서 a에 현재 수를 더하기

- 만약, 현재까지의 부분합에 1을 더한 값보다 현재 수가 크면 반복문을 중단

- 이때, 중단되는 시점에서의 a값은 부분합 중 가장 작은 자연수

- a + 1을 출력하여 문제의 답 출력

 

코드 

# 입력 받기
input()

a = 0  # 부분합을 저장할 변수

# 입력된 수열을 정렬하여 순서대로 처리
for i in [*sorted(map(int, input().split()))]:
    if a + 1 < i:
        break  # 현재까지의 부분합에 1을 더한 값보다 현재 수가 크면 중단
    a += i  # 현재 수를 부분합에 더함

print(a + 1)  # 현재까지의 부분합에 1을 더한 값 출력