# 20210124
# CHAPTER11 Greedy
# Q04 만들 수 없는 금액
# 동전 N개
# 1 <= N <= 1,000
# 1. sorting
# 2. 첫번째 수부터 하나씩 만들 수 있는 숫자 리스트(가상)에 담는다.
# 리스트의 제일 큰 수를 기억하며 담는다.
# 1부터 제일 큰 수 까지 이어져있을 수 밖에 없다.
# (안그러면 이미 정답이 나왔을 것이기 때문)
# 해당 수에 왔을 때 하는 동작
# 2-1 이전의 제일 큰수보다 현재 들어온 값이 2 이상 크면 전의 큰수 + 1이 답이다.
# => 왜냐하면 현재 들어온 값이 이다음 만들 수 중 가장 작기 때문. (이다음 만들 수는 최소 1을 더한 값임)
# 2-2 현재 들어온 값이 이전의 제일 큰 수보다 1 이하로 작으면 기억하고 있던 제일 큰 수를 현재 수를 더한 것으로 교체한다.
# => 현재 수를 더한 것이 가장 큰 수가 될 수밖에 없음.
import sys
sys.stdin = open("input.txt", "r")
def getResult(_list):
ret = 0
max_n = 0
for n in _list:
if max_n + 1 >= n:
max_n += n
else:
ret = max_n + 1
break
return ret
N = int(input())
input_list = list(map(int, list(input().split())))
input_list.sort()
print(getResult(input_list))
Comment