백준 2437번 <저울>

백준 알고리즘 2437번

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

2437번: 저울

---

2437번

입력으로 첫 줄에 저울추의 개수 N이 주어진다. 그 다음 줄에 저울추의 무게를 나타내는 N개의 숫자가 주어진다.

 

출력으로는 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력하면 된다.

---

문제 해결

이 문제는 정렬을 이용하여 해결할 수 있다.

먼저 추들을 정렬하고 작은 숫자부터 만들 수 있는 숫자들을 체크한다.

숫자를 체크하기 위해 ans를 사용한다. 양의 정수 무게 중 최솟값을 출력하는 것이기 때문에 ans는 0이 초기값이다.

 

추의 무게가 ans + 1보다 작거나 같으면 해당 무게를 만들 수 있는 것이기 때문에 ans에 추의 무게를 더한다.

ans가 0부터 시작하기 때문에 처음 추의 무게는 1이어야만 다음 추로 넘어갈 수 있다.

또한 1부터 ans까지의 무게를 만들 수 있기 때문에 다음 추의 무게가 W면 ans + W까지 무게를 만들 수 있다.

 

예를 들어 추가 1, 2, 4이면

1로 무게 1을 만들 수 있어 ans = 1이 되고,

2가 1+1보다 작거나 같기 때문에 무게 3까지 만들 수 있어 ans = 3이 된다.

4가 3+1보다 작거나 같기 때문에 무게 7까지 만들 수 있어 ans = 7이 된다.

 

추가 없기 때문에 ans + 1인 8이 양의 정수 무게 중 최솟값이 된다.

---

코드

N = int(input())
weights = list(map(int, input().split()))
weights.sort()

ans = 0

for w in weights:
    if w <= ans+1:
        ans += w
    else:
        break
print(ans+1)

---

결과

---