문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

입출력 예시

풀이

먼저, N개의 저울추가 있다고 가정해보자.
N개의 저울추를 모두 써서 만들 수 있는 무게를 K라고 한다면, 새로운 추의 무게와 K 사이에 틈이 발생한다면 그 때 측정할 수 없는 무게가 발생하게 된다.

예를 들어, 저울추의 무게가 [1, 2, 4] 가 있다. 이 저울추들로 측정할 수 있는 무게는 1 ~ 7 이다. 새로운 추의 무게를 8이라고 한다면, [1, 2, 4] 저울추로 측정할 수 있는 최대의 무게인 7과 8 사이에는 틈이 발생하지 않고, 측정할 수 있는 무게인 1 ~ 7 에 8을 하나씩 더해본다면 1 ~ 15까지 전부 무게를 측정할 수 있다.

따라서, 저울추의 무게에 앞에서부터 하나씩 접근하면서 저울추의 무게의 합이 다음 저울추의 무게보다 작으면 (정확히는 2 이상의 차이가 나면) 그 때 측정할 수 없는 무게가 발생된다.
ex) [1, 2, 4] 에 9의 새로운 저울추가 추가되면 [1, 2, 4] 로 측정할 수 있는 최대의 무게인 7과 9 사이의 값인 8을 측정할 수 없게 된다.

핵심 요약

1. 수학적으로 조금만 생각해보면 쉽게 풀 수 있는 문제였다.
2. 문제가 어려워 보인다고 겁먹지 말자! 조금만 생각하면 생각보다 가볍게 풀릴 수도 있고, 문제가 어려워보이는 만큼 코드는 쉬울 수 있다.

코드

### 백준 2437

N = int(input())
nums = list(map(int, input().split()))
nums.sort()

target = 1
for num in nums:
	# 타겟에 하나씩 접근하면서 지금까지의 저울추의 합이 다음 저울추보다 낮은지 탐색
    # 차이가 2 이상 나야하기 때문에, 초기 target 값을 1로 설정
    if num > target: 
        break
    target += num
    
print(target)