BOJ 2437번: 저울

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

2437번: 저울

머리가 안돌아가서.. 도저히 풀 수 있는 방법이 생각나지를 않았다. 예시의 답이 1+1+2+3+6+7 = 20 보다 하나 더 큰 수라는 건 알았지만, 그리디를 이용해서 어떤 공식을 찾을 수 있을 지 생각이 나질 않았다. 그래서 질문을 좀 검색해 본 결과..

현재 뽑은 숫자가 지금까지 더한 숫자 보다 작다면 그 수는 지금 까지의 더한 수(SUM) 부터 뽑은 수를 더한 값(SUM + ARR[i]) 까지 만들 수 있고 크다면 지금까지 더한 숫자 +1이 만들 수 없는 최소의 수

라는 걸 찾았고.. 몇 개 해봤더니 맞더라... 그리디 너무 어려워......

import sys

N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

arr.sort()

s = 1
for i in range(N): 
    if (s < arr[i]):
        break
    else:
        s += arr[i]
print(s)