[이코테] 그리디 : 만들 수 없는 금액

🔦 문제

N개의 동전을 가지고 있을 때 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하세요.

입력	출력
5	8
3 2 1 1 9

✍️ 풀이

---

먼저 1 부터 target-1까지 모든 금액을 만들 수 있다고 가정한다.
그리고 target을 현재 동전 단위를 추가해서 만들 수 있는지 확인한다.

• target 보다 작거나 같은 단위가 나와야 그 전 동전 조합을 이용해서 target을 구할 수 있다.

🛠 코드

---

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

target = 1
for x in data:
    # 만들 수 없는 금액일 때 반복종료
    if target < x:
        break
    target += x
print(target)

📝 정리

---

🎈 참고

---

• 이것이 취업을 위한 코딩테스트다 with python