[백준] 저울

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

2437번: 저울

 

재밌는 문제였다. 예를 들어 a1 <= a2 <= a3 <= ... <= an (a 는 양의 정수) 가 있다고 하자.

 

두 번째로 a1, a2, a3, ..., ak 로 1 부터 K 까지의 숫자를 표현할 수 있다고 하자. (K 가 최대이므로 K = a1 + a2 + a3 + ... + ak)

 

a(k+1) 이 (K + 1) 보다 작거나 같다면 1 부터 (K + a(k+1) + 1) 을 포함하고 또한, 두 정수 사이의 정수들을 다 표현할 수 있다. 반대로 크다면 (K + 1) 은 표현할 수 없는 수로 동시에 최소가 된다.

 

import sys

N = int(sys.stdin.readline())
weight = list(map(int, sys.stdin.readline().split()))
weight.sort()
sum = 0

for i in weight:
    if sum + 1 >= i:
        sum += i
    else:
        break

answer = sum + 1

print(answer)