[그리디] 만들 수 없는 금액

1. 문제

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

 

2. 입력

5

3 2 1 1 9

 

3. 출력

8

 

 

그리디 문제,

동전들을 오름차순으로 정렬하고

목표 금액을 만들 수 있는지 여부를 판단하며 값을 증가시킨다.

현재 만들 수 있는 값을 target이라 하면,

현재 target보다 주어진 coin이 크면 해당 금액은 만들 수 없게 된다.

 

1 1 2 3 9가 주어졌을 때,

초기 target = 1 부터 시작한다고 했을 때,

1 ≥ 1 이므로 target += 1 → target=2

두 번째 코인

2 ≥ 1 이므로 target += 1 → target=3

세 번째 코인

3 ≥ 2 이므로 target += 2 → target=5

네 번째 코인

5 ≥ 3 이므로 target += 3 → target=8

다섯 번째 코인

8 < 9 이므로 8이라는 금액은 만들 수 없게 된다.

 

이렇게 된다는걸 따라가면 알기는 하겠지만

원리를 어떻게 생각했는지 솔직히 이해는 잘 안된다.

 

N = int(input())
coins = list(map(int, input().split()))
coins.sort()
target = 1

for coin in coins:
    if target < coin:
        break
    target += coin

print(target)