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

🔔 문제

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.
예를 들어, N=5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.
또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

입력

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

출력

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

🎯 풀이방법

이 문제는 정렬을 이용한 그리디 알고리즘으로 해결할 수 있는 문제이다. 문제 해결 아이디어는 다음과 같다. 일단 동전에 대한 정보가 주어졌을 때, 화폐 단위를 기준으로 오름차순 정렬한다. 이후에 1부터 차례대로 특정한 금액을 만들 수 있는지 확인하면 된다. 1부터 max_coin-1까지의 모든 금액을 만들 수 있다고 가정해보자. 우리는 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 max_coin 금액 또한 만들 수 있는지 확인하면 된다. 만약 max_coin 금액을 만들 수 있다면, max_coin 값을 업데이트하는(증가시키는) 방식을 이용한다. 이러한 원리를 이용하면, 단순히 동전을 화폐 단위 기준으로 정렬한 뒤에, 화폐 단위가 작은 동전부터 하나씩 확인하면서 max_coin 변수를 업데이트하는 방법으로 최적의 해를 계산할 수 있다.

💻 Python 코드

n = int(input())
coins = sorted(list(map(int, input().split())))

max_coin = 1
for coin in coins:
    if max_coin < coin: # 만들 수 없는 금액을 찾았을 때 반복 종료
        break
    max_coin += coin

print(max_coin)