[알고리즘]그리디_만들 수 없는 금액(파이썬 list, tuple, dict, set)(미해결)

['만들 수 없는 금액' 문제 설명]

-난이도 : ★☆☆

-풀이시간 : 30분

-시간 제한 : 1초

-메모리 제한 : 128MB

-기출 : K대회 기출

-출처 : 이것이 코딩테스트다 with 파이썬(p.314)

 

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

 

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

 

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

 

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

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

이때, 각 화폐 단위는 1,000,000 이하의 자연수입니다.

 

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

 

-입력예시 5 3 2 1 1 9

-출력예시 8

 

 

['만들 수 없는 금액' 답안1]

#n을 입력받는다.
n = input();

#금액 n개를 list로 입력받는다.
data = list(map(int, input().split()))
data.sort() #오른차순 정렬한다.

#target은 1부터 시작!
target = 1

for i in data : #i=금액1, 금액2, 금액3...
    #만들 수 없는 금액을 찾았을 때 반복 종료
    #금액이 2가 최소 금액이라면 1이 만들 수 없는 최소금액임!
    if target < i :
        break

    #target증가시키기
    target+=i

print(target)

[설명]

[파이썬]