백준 2437 파이썬(그리디)

한시간 가량 고민하다가 결국 구글에 검색하고야 말았다...ㅠㅠ

 

이 문제를 푸는 아이디어는 누적합까지는 모든 무게의 경우를 만들 수 있다는 것이다.

예를 들어 1,2,3의 추가 있다고 한다면

누적합 6(1+2+3) 까지의 무게를 무조건 만들 수 있다는 것이다.

그리고 이 누적합+1 의 값보다 큰 추가 다음으로 나온다면 (예를들어 8이 나온다면) 누적합 +1(7) 이 주어진 추들로 측정할 수 없는 양의 정수 무게중 최소값이다.

 

누적합까지의 모든 경우의 수가 만들어 질 수 있다는 아이디어,  이건 평소 숫자에 대해서 얼마나 친한지?, 센스인것 같다. 내 머리가 조금 딱딱한 듯 하다... 더 유연하게 생각할 수 있기를! 

이런 방법도 있음을 기억해두자.

 

# 2437번: 저울

n = int(input())
scale = list(map(int,input().split()))
scale.sort()

weight = 1
for i in scale:
    if weight < i:
        break
    weight += i
print(weight)