그리디 알고리즘: 거스름돈, 만들 수 없는 금액(이코테 예제)

그리디 알고리즘(Greedy Algorithm)

• 탐욕적으로 문제를 푸는 알고리즘
• 현재 상황에서, 탐욕적으로 좋은 것(최적해)를 선택하는 방법
• 단순하게 탐욕적으로 최적해를 선택한다.

---

예제 1: 거스름돈

거스름돈으로 사용할 수 있는 금액은 500원, 100원, 50원, 10원짜리 동전이며 무한히 존재한다. 손님에게 거슬러줘야 할 돈이 N원일 때, 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러줘야할 돈 N원은 항상 10의 배수이다.

 

예제의 아이디어는 '가장 큰 화폐단위부터' 탐욕적으로 선택하며 돈을 거슬러주는 것이다. 동전의 최소 개수를 구해야하므로, 가장 큰 화폐단위를 선택해야 동전의 개수를 줄일 수 있다. 가장 큰 화폐단위부터 거슬러줘야할 돈을 나눈 후, 나누어 떨어지지 않으면 작은 화폐단위로 넘어가는 것이다

답안 코드

n = int(input())  # 거슬러줘야 할 돈 입력
coins = [500, 100, 50, 10]  # 사용할 수 있는 동전 단위

count = 0   # 동전의 개수
for c in coins:
    count += (n // c)  # 거스름돈(n)을 동전(c)으로 나누어 그 몫을 동전의 개수에 더한다
    n %= coin # 거슬러주고 남은 돈을 업데이트
    
# 최종 동전의 개수 출력
print(count)

 

---

예제 2: 만들 수 없는 금액

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

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

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

입력 예시	출력 예시
5 3 2 1 1 9	8

 

'만들 수 있는 값'을 target으로 정한 후, 가지고 있는 화폐 단위(coin)을 더하여 다음 수를 만들 수 있는지 없는지를 확인한다.  target을 1로 설정하고, 차례대로 coin을 더해나간다면, target-1값 까지는 더해진 coin으로 만들 수 있는 수가 된다. 즉, target값은 현재까지 더해진 coin으로 만들 수 있는 최대값+1이다. 따라서 반복문을 돌며 다음으로 더해질 coin을 확인한다. 만약 다음 coin이 target값보다 크거나 없다면, 현재의 target값은 만들 수 없는 수가 되므로, 정답이 된다.

예시 1

 

입력	출력
4 1 2 3 5	12

풀이

target	coin	target+coin	더해진 coin	해석
1	1	2	[1]	coin으로 1까지 만들 수 있다
2	2	4	[1, 2]	coin으로 3까지 만들 수 있다
4	3	7	[1, 2, 3]	coin으로 6까지 만들 수 있다
7	5	12	[1, 2, 3, 5]	coin으로 11까지 만들 수 있다
12	None			주어진 coin으로 12를 만들 수 없음

 

 

예시 2

입력	출력
5 3 2 1 1 9	8

풀이

target	coin	target+coin	더해진 coin	해석
1	1	2	[1]	coin으로 1까지 만들 수 있다
2	1	3	[1, 1]	coin으로 2까지 만들 수 있다
3	2	5	[1, 1, 2]	coin으로 4까지 만들 수 있다
5	3	8	[1, 1, 2, 3]	coin으로 7까지 만들 수 있다
8	9			coin(9)이 target(8)보다 크다: 주어진 coin으로 8을 만들 수 없음

 

n = int(input())  # 코인의 개수
coins = list(map(int, input().split()))  # 코인(화폐) 단위

coins.sort() # 오름차순 정렬

target = 1
for c in coins:
    if target < c:  # coin이 target보다 크다면 target을 만들 수 없음
        break
    target += c  # coin이 target보다 작거나 같다면 target을 만들 수 있음, 더해주기

print(target) # 만들 수 없는 수 출력