그리디 알고리즘 : 만들 수 없는 금액

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

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

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

 

input :

5

3 2 1 1 9 ----> 8

 

설명 : 이 문제는 많이 어려웠다.. 그런데 난이도가 하인 문제.. 아무래도 그리디에 익숙하지 않으면 풀 수 없는 문제인가보다. 위 리스트를 정렬하면 1, 1, 2, 3, 9가 된다.

우선 1원을 만들 수 있는지 살펴보자. (target = 1, target의 의미는 target -1까지의 숫자를 만들 수 있다는 뜻.)

첫 번째 요소를 꺼내면 1이다. 만일 꺼낸 값이 1이 아니라 2나 그 이상의 숫자이면 만들 수 없을 것이다.

(if target < i : break, i는 꺼낸 요소의 값)

target과 꺼낸 요소는 1이기 때문에 1을 만들 수 있다.

target과 꺼낸 요소를 더해주면 2가 된다. (1까지 만들 수 있다는 뜻.)

그 다음 요소를 꺼내준다. (i = 1, target이 꺼낸 element 보다 크다.)

target과 더해준다. (target = 3, 2까지 만들 수 있다는 의미)

이 과정을 반복한다.

 

위 과정이 잘 이해가지 않을 수 있다. 특히 target(-1까지 숫자를 만들 수 있다.)와 target이 i 보다 작을 경우(target의 숫자를 만들 수 있는 지 여부를 확인하는 것) 루프를 중지하는 것, target과 리스트에 꺼낸 요소를 더하는 것 (만들 수 있는 숫자의 -1에 해당 요소의 값을 더해주면 target 값의 -1만큼의 값을 만들 수 있다.) 이 부분이 이해가 안 갈 것이다.

나도 설명 못할 것 같다. ㅠㅠ 그냥 반복해서 풀다보니 익숙해진 것 같다. 알아서 하시길..

 

n= int(input());
coin_list = list(map(int,input().split()))

result = 1

coin_list.sort()

for i in coin_list :
  if result < i:
    break
  result += i;

print(result)