99클럽 코테 스터디 24일차 (BOJ 2437 저울)

오늘의 문제: BOJ 2437(저울)

문제 설명

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

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

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

문제 풀이

이 문제의 경우 사용된 알고리즘과 코드는 간단한데 그리디라는 접근 방법을 떠올리는게 쉽지 않은 문제 였습니다. 주어진 예시로 문제 풀이를 진행하면 먼저 저울의 무게를 오름차순으로 정렬해줍니다. [1, 1, 2, 3, 6, 7, 30] 그 다음 만약 저울추가 1만 주어진다면 무게의 최소값은 2가 될것입니다. [1, 1]이 주어지면 3이될것입니다. 만약 [1, 3] 이 주어지면 2가 될것입니다. 정렬한 순서대로 무게를 더해가면 모두 더한 수가 다음 무게보다 작을 경우 측정할 수없는 최소 무게가 될 것입니다.

[1, 1, 2, 3, 6, 7, 30] 의 경우

1. 1을 사용 1까지 측정 가능 (1)

2. 1을 사용 2까지 측정 가능  (1, 2)

3. 2를 사용 4까지 측정 가능  (1, 2, 3, 4)

4. 3을 사용 7까지 측정 가능  (1, 2, 3, 4, 5, 6, 7)

5. 6을 사용 13까지 측정가능  (1, 2, 3, 4, 5, 6, 7 ~ 13)

6. 7을 사용 20까지 측정가능  (1, 2, 3, 4, 5, 6, 7, 8, 9 ~ 20)

7. 30을 사용 (1~20, 31~50) 측정 가능

측정할수 없는 최소 무게는 21

n = int(input())
num_list = list(map(int, input().split()))
sort_list = sorted(num_list)

weight = 1

for num in sort_list:
    if weight < num:
        break
    else:
        weight += num
       
answer = weight        
print(answer)