[이코테] Greedy - 만들 수 없는 금액

문제

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

입력조건

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

출력조건

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

입력예시

5
3 2 1 1 9

출력예시

8

풀이

아이디어

• 제일 작은 수부터 비교하기 위해 양의 정수 리스트를 오름차순으로 정렬한다.
• target 을 1로 설정한다.
• target 이 가지고 있는 동전 리스트 중 어떤 수보다 작은 수 이면 그 아래 수까지 만들 수 있는 것이다.
• 복습요망

coin_num = int(input())
coin_list = list(map(int, input().split(" ")))

coin_list.sort()

target = 1

for i in coin_list:
    if target < i:
        break
    target += i

print(target)