[이취코테] 만들 수 없는 금액

문제

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

 

입력 조건: 

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

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

 

정답 코드

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

target = 1
for x in data:
    if target < x:
        break
    target += x
    
print(target)

이 문제를 봤을 때 그리디 알고리즘을 사용하기 위해 화폐를 오름차순으로 정렬해야 하는 것 까진 떠올렸지만 그 후 아이디어를 떠올리지 못해 결국 풀지 못해 풀이를 보고 다시 풀어보았다. 풀이 방법은 1부터 차례대로 특정한 금액을 만들 수 있는 지 확인하는 것이다. 현재 확인하는 동전을 이용해 target 금액을 만들 수 있는지 확인하고 만들 수 있다면 target 금액을 증가시키는 방식이다.

 

현재 확인하는 동전의 단위가 target보다 크다면 target을 만들 수 없다. 예를 통해 확인해보자.1을 확인하고 target을 2로 증가시킨 상태에서 다음 동전이 1이라면 1 + 1로 2를 만들 수 있고 다음 동전이 2라면 당연히 2를 만들 수 있다. 하지만 다음 동전이 3이상이라면 2를 만들 수 없다. 

 

배울 점

그리디 알고리즘의 대표 문제인 거스름돈 문제와 비슷할 줄 알았는데 여기서는 동전의 수가 한정적이라는 것 때문에 아이디어를 떠올리는 것이 쉽지 않았다. 더 많은 문제를 풀어보면서 아이디어 도출 능력을 키워야겠다.

 

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)