측정할 수 없는 최소 무게
면접 대비시간 제한1초메모리 제한128 MB
한쪽 저울판에만 올릴 수 있는 정수 무게추들이 주어질 때, 부분집합 합으로 만들 수 없는 가장 작은 양의 정수를 구합니다.
문제
양팔 저울 하나로 물건의 무게를 재려고 한다. 저울의 양쪽 팔 길이는 같고, 각 끝에는 물건이나 추를 올리는 접시가 있다. 이 문제에서는 한쪽 접시에는 추만 올릴 수 있고, 다른 쪽 접시에는 무게를 재려는 물건만 올릴 수 있다.
양의 정수 무게를 가진 N개의 추가 주어진다. 주어진 추들 중 일부를 골라 추를 올리는 접시에 놓을 때, 잴 수 없는 양의 정수 무게 중 가장 작은 값을 구하라.
예를 들어 무게가 3, 1, 6, 2, 7, 30, 1인 7개의 추가 있으면, 이 추들로 잴 수 없는 양의 정수 무게 중 가장 작은 값은 21이다.
입력
첫째 줄에 추의 개수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에 각 추의 무게를 나타내는 양의 정수 N개가 공백으로 구분되어 주어진다. 각 추의 무게는 1 이상 1,000,000 이하이다.
출력
주어진 추들로 잴 수 없는 양의 정수 무게 중 가장 작은 값을 첫째 줄에 출력한다.