[그리디] 만들 수 없는 금액 (파이썬)

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

---

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

print(min(coins))
result = 0

if min(coins) != 1:
  result = 1

elif min(coins) == 1:
  coin = coins[:n-1:]
  i = 0
  sum = 0
  while i<len(coin):
    sum += coin[i]
    i += 1

  p = max(coins) - sum
  if p == 0 or p >= 2:
    result = sum + 1
  elif p == 1:
    result = max(coins) + 1
  
print(result)

1. 가지고 있는 코인들 중 가장 적은 수가 1보다 크다면, 만들 수 없는 최소 금액은 '1'

2. 가지고 있는 코인들 중 가장 적은 수가 1이라면,

       가장 큰 수의 코인을 제외하고 나머지 코인들의 수를 더함

       그 합이 

          1) 가장 큰 값과 같을 때 or 가장 큰 값과 2 차이 날 때 : 합보다 1 큰 수가 만들 수 없는 최소 금액

          2) 가장 큰 값과 1 차이 날 때 : 가장 큰 값보다 1 큰 수가 만들 수 없는 최소 금액

sum	max	result
7	7	8
7	9	8
7	8	9