[BOJ] 2437번 - 저울 (Python)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

우선 예시 중에서 추 [1, 1, 2]만 가지고 있다고 생각해보자.

그러면 측정할 수 있는 무게는 위의 그림과 같다.

다른 예시로 [1, 2, 3]으로 생각해보면,

1 = 1
2 = 2
3 = 3
4 = 1+3
5 = 2+3
6 = 1+2+3

위와 같이 측정할 수 있다. 

즉, 가지고 있는 추들의 무게를 합한 값 이하의 값들은 측정할 수 있다는 것을 알 수 있다.

단, 추의 무게들이 정렬이 되어있어야 하며 추와 추 사이의 무게 차이가 크게 나면 안된다.

여기서 추 사이의 무게 차이가 얼마만큼 차이가 나면 안되는지를 생각해봐야한다.

문제에서 주어진 예시로 현재 [1, 1, 2, 3]의 추를 가지고 있어 7까지 측정할 수 있다고 하자.

다음 추가 현재 측정할 수 없는 8보다 작거나 같은 6이면 7 + 6 = 13 까지 측정할 수 있을 것이다.

그러나 그림에서와 같이 [1, 1, 2, 3, 6, 7]은 20까지 측정할 수 있는데 다음 추가 30이면 21부터 29까지는 측정할 수 없을 것이다.

이와 같은 규칙을 이용해 문제를 해결했다.

1. 추의 무게를 오름차순으로 정렬한다.
2. 가장 작은 추의 무게가 1이 아닐경우
    → 측정할 수 없는 가장 작은 양의 정수 무게는 1이다.
3. 가장 작은 추의 무게가 1일 경우
    → [(t : 현재 측정할 수 있는 가장 큰 무게) + 1 = 현재 측정할 수 없는 가장 작은 무게] 와 다음 추의 무게 비교
        → t + 1 >= 다음 추의 무게 : t 증가
        → 아닐 경우 : break

---

🍀 풀이 🍀

import sys

input = sys.stdin.readline

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

if nums[0] > 1 :
    print(1)
else : 
    t = nums[0]
    for i in range(1, n) :
        if t + 1 >= nums[i] :
            t += nums[i]
        else :
            break
    print(t + 1)