만들 수 없는 금액 - python

만들 수 없는 금액

문제

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

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

입력 조건

첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1 <= N <= 1000)

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

출력 조건

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

입력 예시

5
3 2 1 1 9

출력 예시

8

핵심 아이디어

만들고자 하는 금액을 1로 하고 주어진 동전들을 작은 수부터 차례대로 더함

이때 더하는 동전의 단위가 이미 더해진 값보다 크면 만들 수 없는 금액임

PseudoCode

1. 입력 (Input)
   • 공백 구분, 리스트로 입력 받음
2. 처리 (Process)
   • 만들고자 하는 금액 (target) = 1 선언
   • 입력 받은 동전을 작은 수부터 정렬
   • for 문으로 target에 동전을 작은 수부터 더함
     • 더할 값이 target보다 크면 target은 만들 수 없는 수
3. 출력 (Output)
   • target 출력

문제 풀이

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

출저

이것이 취업을 위한 코딩 테스트다 with 파이썬
저자 : 나동빈