[백준] 저울(2437) - python

✏️ 문제

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

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.
예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

🎈 입력

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

🎈 출력

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

🎈 입출력 예

<입력>
7
3 1 6 2 7 30 1

<출력>
21

👩‍💻 내 코드

이번 문제는 이해하기 쉬웠지만 아이디어를 떠올리기 힘들었다. 결국 구글링의 도움으로 문제를 풀 수 있었다. 이 곳에서 도움을 받았으며, 알고리즘은 아래와 같다.

1. 추의 무게를 오름차순으로 정렬한다.
2. 이전 추 무게의 합 + 1 >= 추의 무게

위의 아이디어를 이용해 아래와 같이 코드를 구현했다. 사실 아이디어만 떠올리면 코드 짜는 것은 굉장히 쉬웠다.

N = int(input())

numbers = list(map(int, input().split()))
numbers.sort()

sum_num = 0
for i in range(N):
    if sum_num +1 >= numbers[i]:
        sum_num += numbers[i]
    else:
        break
print(sum_num + 1)

뭔가 혼자서 끝까지 풀어도 규칙을 발견할 수 있었을까 싶다... 문제 보자마자 바로바로 규칙을 찾을 수 있었으면 좋겠다.