처음에는 모든 경우를 구하는 방식으로 풀어보려고 하였다. 그러나 아무리 생각해보아도 연산 사이클이 너무 커질 것 같아서 다른 방법을 생각해보다가 결국 구글링을 통해 힌트를 얻을 수 있었다.

추의 무게를 담은 배열을 오름차순으로 정렬한 뒤에 이전 추들의 누적합+1이 현재 추의 무게보다 가벼울 경우 이전 추들의 누적합+1이 측정할 수 없는 무게가 되는 규칙이었다.

예제로 주어진 3 1 6 2 7 30 1은 오름차순 정렬을 통해 1 1 2 3 6 7 30이 된다. 누적합+1을 total이라고 했을 때 누적합+1이므로 total은 1부터 시작한다.

• total(1)은 1보다 크거나 같으므로 total에 1을 더해준다. total은 2가 된다.
• total(2)은 1보다 크거나 같으므로 total에 1을 더해준다. total은 3이 된다.
• total(3)은 2보다 크거나 같으므로 total에 2를 더해준다. total은 5가 된다.
• total(5)는 3보다 크거나 같으므로 total에 3을 더해준다. total은 8이 된다.
• total(8)은 6보다 크거나 같으므로 total에 6을 더해준다. total은 14가 된다.
• total(14)는 7보다 크거나 같으므로 total에 7을 더해준다. total은 21이 된다.
• total(21)은 30보다 작으므로 순회를 멈춘다.

결과값은 21이 되는 것을 알 수 있다. 이러한 규칙을 통해 코드를 구현하였다.

• n을 입력받는다.
• 추의 무게를 저장하는 배열 weight를 선언하고 추의 무게를 입력받는다.
• weight를 오름차순 정렬한다.
• 누적합+1에 해당하는 변수 total을 1로 정의한다.
• weight배열을 순회하는 i에 대한 for문을 돌린다.
  -> 만약 total이 i보다 작을 경우 반복문을 탈출한다.
  -> total에 i를 더한다.
• total을 출력한다.

Code

n=int(input())
weight=list(map(int, input().split()))
weight.sort()
total=1
for i in weight:
    if total<i:
        break
    total+=i
print(total)