만들 수 없는 금액 [그리디] *

#n개의 동전 이용, 만들 수 없는 금액 최솟값

n=int(input())
array=list(map(int,input().split()))
array.sort()
target=1

for coin in array:
    # 만들 수 없는 금액을 찾았을 때
    if target<coin:
        break
    else:
        target+=coin

print(target)

• 40분 걸렸는데 결국 못 풂.
• 주어진 코인으로 target 금액을 만들 수 있는지 여부를 체크.
• 먼저 target을 1로 설정. 꺼낸 coin이 target보다 크다면 만들 수 없음. 작다면, 이미 target보다 작은 coin은 target을 만들 수 있다는 것. 따라서 target<coin 조건만 확인하면 됨.
• 코인이 모두 1보다 크다면 만들 수 없는 양의 정수는 무조건 1이 됨.
• 만들 수 없는 금액의 최솟값은 어떠한 coin(i) 보다 작은 (coin의 합+1)이 됨. 따라서 target을 1로 설정해놓고 여기에 코인을 더하면서 값 확인