[백준] 2437 - 저울

https://www.acmicpc.net/problem/2437

2437번: 저울

알고리즘 스터디에서 '정렬' 연습문제로 풀게된 문제였다.

---

풀이 아이디어

내가 떠올린 기본적인 알고리즘은 다음과 같다.

 

1. 입력받은 추를 무게순으로 오름차순 정렬한다.

2. 추를 앞에서 하나 가져와서 "추 그룹"에 추가한다.

3. 추 그룹의 무게 합과 다음 추의 무게를 비교한다.

 

만약 다음 추의 무게가 '추 그룹의 무게합 + 1' 보다 크면,

어떤 방법을 써도 '추 그룹의 무게합 + 1' 의 무게는 잴 수 없다.

따라서 '추 그룹의 무게합 + 1'이 정답이 된다.

 

단 여기에는 한가지 조건이 필요하다.

추 그룹에 반드시 '1'이 포함되어 있어야 한다.

만약 1이 없다면, 1g 의 무게를 재지 못하기 때문에 '추 그룹의 무게합 + 1'은 의미가 없다.

수학적 귀납법과 느낌이 비슷하다.

---

정답 소스 코드

n = int(input())
nums = list(map(int, input().split()))
nums.sort()
s = nums[0]
answer = 1
if s == 1:
    for i in range(1, n):
        if s+1 < nums[i]:
            break
        s += nums[i]
    answer = s+1
print(answer)