그리디 - 만들 수 없는 금액 - 2021/03/08

동전의 화폐 단위가 주어질 때 이를 조합해서 만들 수 없는 최솟값 구하기

 

ex) 3 2 1 1 9 -> 8원이 만들 수 없는 최솟값

ex) 3 5 7 -> 1원이 만들 수 없는 최솟값

 

이 문제는 초기에 알고리즘을 어떻게 구성할 것인지 생각하는게 어려운 문제

 

먼저 정렬을 한 후 가상의 최소값 1을 잡아 순서대로 더해나간다. 더해진 숫자 이전까지는 구할 수 있다는 뜻

 

ex) 1 1 2 3 9 에서 최소값 1에 1을 더하면 2, 2에 1을 더하면 3, 3에 2를 더하면 5 인데 여기까지 했을 때, 4까지는 구할 수 있다는 뜻이고 5는 모른다. 계속 더해나가면 5+3 = 8이므로 8 이전까지는 더할 수 있다. 그러나 뒤에 9가 있기 때문에 8은 나올 수 없다.

 

-> 조건문을 걸어서 뒤에 더하려는 숫자보다 숫자의 합이 작으면 break한다.

 

n=int(input())
5
data=list(map(int,input().split()))
3 2 1 1 9
data.sort()


num=1
for i in data:
    if num<i:
        break
    num+=i
    
    
print(num)
8

 

 

초기에 가상의 최소값 1을 생각한다는게 어려운 문제였다.