[백준] 2437. 저울

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

2437번: 저울

 

풀이를 생각해내기 쉽지 않았던 문제.

 

풀이

입력된 숫자 배열을 오름차순으로 정렬한 후 검사.

 

만약 [이전의 숫자들을 더한 결과 + 1] < [다음 숫자] 라면,

더해서 만들 수 없는 수가 생기게 됨.

• EX 1 - [1, 2, 2, 7, 9, 13, 15]

  • 1+2+2 + 1 < 7 이므로 '6' 을 만들 수 없음

 

• EX 2 - [1, 1, 4, 9, 13]

  • 1+1 + 1 < 4 이므로 '3' 을 만들 수 없음

 

• EX 3 - [1, 1, 2, 3, 6, 7, 19, 23]

  • 1+1+2+3+6+7 + 1 = 21 > 19 이므로 1 ~ 19의 모든 값을 만들 수 있음
  • 1+1+2+3+6+7+19 + 1 > 23 이므로 1 ~ 23의 모든 값을 만들 수 있음
  • 1+1+2+3+6+7+19+23 = 62 이므로 1 ~ 62의 모든 값을 만들 수 있고, 63부터 만들 수 없음.

---

원리를 간단하게 이해해 보자면,

배열 [n1, n2, n3, n4, .....] 가 존재한다고 가정할 때,

만약 n1, n2, n3 이 [1 ~ 6] 까지의 숫자를 만들 수 있다면 (n1+n2+n3 = 6),

n1, n2, n3, n4는 [1 ~ 6], [n4 ~ n4+6] 까지의 숫자를 만들 수 있을 것이기 때문에, 7 < n4 이면 7을 만들 수 없게 됨.

 

import sys
read = sys.stdin.readline

N = int(read().strip("\n"))
a = list(map(int, read().strip("\n").split()))

a.sort()
sum = 0
answer = 0

if a[0] > 1:
    answer = 1
else:
    for i in a:
        if sum + 1 < i:
            break
        sum += i

# answer에 값이 담기지 않았을 때 (배열 내 최댓값보다 작은 모든 값을 구현 가능)
# 에는 모든 값의 합 + 1이 답이 됨.
answer = sum + 1

print(answer)