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

🍏 문제

---

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

예를 들어, N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐단위)동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원 입니다.

또 다른 예시로, N = 3이고 각 동전이 각각 3원, 5원, 7원짜리 (화폐 단위) 동전이라고 가정합니다. 이떄 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원 입니다.

📄 코드

---

n = int(input())
coin = list(map(int, input().split()))

coin.sort()
target = 1

for x in coin:
    if target < x:
        break
    target += x

print(target)

✍ 풀이

---

💡 target보다 작은 값은 모두 만들 수 있다.
동전의 리스트를 오름차순으로 정렬한 뒤 target을 1로 설정한다. 동전이 target보다 크지 않은 경우에 target에 해당 동전의 값을 더한다. 만일 동전의 값이 target보다 크다면 해당 target은 만들지 못한다.