만들 수 없는 금액

문제

동네 편의점의 주인인 velmash는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

입력조건

첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1 <= N <= 1,000)
둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수 입니다.

출력조건

첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

입력예시

5

3 2 1 1 9

출력예시

8

풀이

1. a는 검사할 값이고 1부터 시작한다.
2. 입력받은 화폐 단위들을 리스트에 넣고 오름차순 정렬한다.
3. a와 리스트를 비교한다.
4. 1은 1로 만들 수 있으므로 a에 1을 더한다.
5. a=2이고 2는 1+1로 만들 수 있으므로 a에 1을 더한다.
6. a=3이고 3은 3으로 만들 수 있으므로 a에 3을 더한다.
7. a에 3을 더하는 이유는 5까지의 모든 금액을 만들 수 있기때문이다.
8. 이런식으로 a를 만들 수 있으면 a에 해당 화폐 금액을 더해주고 만들 수 없으면 그때의 a값이 답이된다.

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

a=1
for i in arr:
    if a < i:
        break
    a += i
    
print(a)