[이코테] 그리디 - 만들 수 없는 금액 python

난이도 : ●○○ | 풀이 시간 : 30분 | 시간 제한 : 1초 | 메모리 제한 : 128MB | 기출 : K 대회 기출

 

문제

• 동빈이는 N개의 동전을 가지고 있다.
• N개의 동전을 이용해 만들 수 없는 양의 정수 금액 중 최소값을 구하는 프로그램을 작성하라.

 

입력조건

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

출력조건

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

 

입력예시

5
3 2 1 1 9

출력예시

8

 

 

아이디어

• 동전들을 화폐가치의 오름차순으로 정렬한다
• 동전을 하나씩 꺼내보면서 만들 수 있는 금액인지 확인한다

 

입력예시처럼 N = 5, coins = [3, 2, 1, 1, 9]일 때를 생각해보자

 

1. coins.sort() -> [1, 1, 2, 3, 9]

2. coins[0]인 1원 추가 -> 1원 만들 수 있음

3. coins[1]인 1원 추가 -> 1, 2원 만들 수 있음

4. coins[2]인 2원 추가 -> 1, 2, 3, 4원 만들 수 있음

5. coins[3]인 4원 추가 -> 1, 2, 3, 4, 5, 6, 7원 만들 수 있음

6. coins[4]인 9원 추가 -> 1, 2, 3, 4, 5, 6, 7원 / 9, 10, 11, 12, 13, 14, 15, 16원 만들 수 있음

→ 8원을 만들 수 없음

만들 수 있는 가장 큰 금액(target)+1보다 더 큰 값의 화폐가 들어오면 target+1을 만들 수 없음

 

 

 

코드

n = int(input())
coins = list(map(int,input().split()))
coins.sort()
result = 0
for coin in coins:
    if result+1<coin:
        break
    result += coin

print(result+1)