[Python] 만들 수 없는 금액

문제

• N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요
• 예를 들어, N = 5이고, 각 동전이 3원, 2원, 1원, 9원짜리 동전이라고 가정합시다
• 이 때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟 값은 8원입니다

입력

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

출력

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

문제 풀이

• 동전의 금액을 오름차순으로 정렬
• 오름차순으로 정렬 한 동전들을 더해가면서 만들 수 있는 값(target) 업데이트
• 만약 target 값보다 동전의 금액이 큰 경우 그 target 값을 만들 수 없으므로 break
• target 값 출력

코드

n = int(input())
data = list(map(int,input().split()))
data.sort()
target = 1
for i in data:
    if target < i:
        break
    target += i
print(target)