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

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

동네 편의점의 주인인 동빈이는 N개의 동전을 갖고 있다. 이 때 N개의 동전을 이용해 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성해라.

입력조건

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

출력조건

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

사고과정

• 그리디 카테고리인데 도저히 아이디어가 생각이 안나서 DP로 풀어보려고 했으나 실패했다. 시간을 충분히 가져도 해결 아이디어가 떠오르지 못했다. 만들 수 '없는' 금액의 유형은 처음이라서 어떻게 할 줄 몰랐다. 책을 보니 정렬을 이용한 그리디 알고리즘이었다.
• 책 풀이를 보아도 단 번에 이해가지 않았다. 핵심 포인트는 "주어진 화폐 단위 하나씩 loop를 도는데, 이때 동시에 만들 수 없는 금액을 1원 부터 시작해서 특정 조건에 부합하면 바로 break" 하는 것이다. 이 때, '특정 조건'이란, 만들 수 있는지 없는지 판단하는 금액 >= 확인하고 있는 화폐 단위를 의미한다.
• 예를 들어, 주어진 화폐 단위가 [1, 2, 5] 라고할 때, 1원 부터 확인하자. 동시에 만들 수 있는지 확인하는 금액도 1원부터 시작한다. 1원을 1원 동전으로 만들 수 있으므로 가능하다. 이때, 만들기 가능 여부 확인 금액 + 사용한 화폐 단위를 더해 1+1 = 2원으로 만들기 가능 여부 확인 금액을 업데이트 시켜준다. 다음은 2원이다. 2원 동전으로 만들 수 있기 때문에 가능하다. 따라서 2 + 2 = 4원으로 만들기 가능 여부 확인 금액을 업데이트 시켜준다.(이 때 4원이라함은 1~3원까지는 주어진 화폐 단위 [1, 2]로 만들수 있음을 의미한다) 다음확인할 화폐는 5원이다. 가능 여부 확인 금액은 4원인데, 확인하는 화폐 단위 5원이 더 크다. 그러므로 4원은 주어진 화폐 단위 [1, 2, 5]로 만들 수 없는 금액 중 최솟값이 된다.

풀이(스스로 못 푼 풀이)

import sys

n = int(input())
currency = list(map(int, input().split()))
currency.sort()

target = 1
for c in currency:
    if target >= c:
        target += c
    else:
        break

print(target)