그리디 : 만들 수 없는 금액

25/03/06

문제

Q) 만들 수 없는 금액
동전 여러 개가 주어질 때, 이 동전들로 만들 수 없는 가장 작은 금액을 구하는 문제.

입력 예)
동전 : [3, 2, 1, 1, 9]
출력 예)
8

내 풀이

1. data 가장 작은 동전부터 오름차순 정렬
2. data list 에서 젤 작은애부터 + 해주면서
   target (최대값) < 동전
   이면 target이 정답
   다 돌때까지 target >= 동전
   이면 target이 정답임

코드

data = list(map(int,input().split()))
target = 1

data.sort()
print(data)

for i in data:
  if i > target :
    print('answer', target)
    break
  target += i
  print(target)

Fail 인 이유

• target += i 가 이해 안감,, 왜 저렇게 하면 더할 수 있는 모든 숫자가 나오는지,,?