[Beakjoon] 2437 : 저울 - python

문제

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

 

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

 

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

 

▶️ 입력 조건 

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

▶️ 출력 조건

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

---

풀이

해당 문제는 무려 5번의 오답을 거친 후에도 해결하지 못해 해설을 본 문제다.

 

우선 해당 문제를 처음 읽어보았을 때 단순하지만 무식하게 생각했다.

1부터 1,000,000까지 하나씩 모든 정수를 가지고 있는 추와 견주어 측정할 수 있는지에 대한 여부를 확인하는 로직을 구현했고,

로직상 문제는 없을 것 같지만 시간초과로 대부분 오답을 맞이했다.

 

그래서 도저히 아닌 것 같아서 주어진 추를 가지고 정답을 찾아내려고 노력해보았으나 감이 잡히질 않아서 해설을 찾아봤다.

소스코드를 찾아보는 것이 아닌 해설을 찾아본 후 해설을 읽고 코드를 짜보는 과정을 거쳤다.

 

우선 예시로 주어진 추를 가지고 풀이를 해보겠다.

 

>> 3 1 6 2 7 30 1

 

해당 추를 정렬을 한다. 

 

>> 1 1 2 3 6 7 30

 

정답을 구하는 방법은 각 요소가 하나씩 추가된다고 가정하고 누적합을 구하여 바로 뒤에 오는 숫자와 크기를 비교하는 방법이였다.

이해가 잘 가지 않을테니 설명을 해보겠다.

• 1 => 1까지 측정 가능
• 1 + 1 => 2까지 측정 가능
• 1 + 1 + 2 => 4까지 측정 가능
• 1 + 1 + 2 + 3 => 7까지 측정 가능

이런식으로 요소를 하나 추가할 때 마다 측정 가능한 최대 값이 달라진다.

이때 요소를 추가할 때 다음에 오는 요소가 측정할 수 있는 값보다 클 경우 문제가 생긴다. 

이어서 설명해보겠다.

• 1 + 1 + 2 + 3 => 7까지 측정 가능

7까지 측정이 가능하기 때문에 3 다음에 6이 요소로 들어오는 것은 문제가 되지 않는다.

왜? 이미 7까지 측정이 가능하기 때문이다. 6은 7보다 작은 값이기 때문이다.

• 1 + 1 + 2 + 3 + 6 => 13 까지 측정 가능

이 다음 7이 요소로 오는 것 또한 문제가 되지 않는다.

왜? 이미 7은 13으로 측정할 수 있는 값이기 때문이다.

• 1 + 1 + 2 + 3 + 6 + 7 => 20 까지 측정 가능

그러나 이 다음이 문제다. 7다음으로 오는 숫자는 30이다.

현재 7까지 가지고 있는 추로는 20kg까지 측정할 수 있다.

그러나 30kg가 추가 되어 버리면? 21kg ~ 29kg까지 측정할 수 있는 방법이없다.

 

30을 제외한 추로는 20kg까지 밖에 측정할 수 없기 때문이다.

그렇기 때문에 정답은 21kg가 되는 것이다.

 

이 과정을 완벽하게 이해하고 코드를 구현해봤다.

 

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

result = 1

for num in numbers:
    
    if result < num :
        break
    
    result += num
    
print(result)