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

난이도: 1 / 풀이 시간: 30분

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

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

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

입력 조건

• 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1 ≤ N ≤ 1,000)
• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합 니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수입니다.

출력 조건

• 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

입력 예시

5
3 2 1 1 9

출력 예시

8

---

풀이 특징

• 현재까지 만들 수 있는 금액을 target-1 라고 가정
• target 금액을 현재 coin 으로 만들 수 있는지 비교
• 만들 수 있다면 target += coin 업데이트 (target-1 금액에 coin 더한금액들 모두 만들 수 있음)
• 아닌 경우 해당 target 금액 반환

# 만들 수 없는 최솟값
n = int(input())
coins = list(map(int, input().split()))
coins.sort()
# 1 1 2 3 9
target = 1
for coin in coins:
    if coin <= target:
        target += coin
    else:
        break

print(target)