문제 7)

한국에는 다음과 같이 8가지 종류의 화폐가 있습니다.

• 동전 : 10원, 50원, 100원, 500원
• 지폐 : 1,000원, 5,000원, 10,000원, 50,000원

손님에게 거슬러줘야 하는 금액이 주어질 때, 거슬러주는 동전과 지폐 개수의 합이 최소가 되도록 하려고 합니다.

예를 들어 거슬러줘야 할 금액이 2,760원 이라면, 1,000원짜리 2장, 500원짜리 1개, 100원짜리 2개, 50원짜리 1개, 10원짜리 1개를 거슬러줄 때 동전과 지폐 개수의 합이 최소가 됩니다.

손님에게 거슬러줘야 하는 금액 money가 매개변수로 주어질 때, 거슬러 주는 동전과 지폐 개수합의 최솟값을 return 하도록 solution 함수를 작성하려 합니다. 빈칸을 채워 전체 코드를 완성해주세요.

---

매개변수 설명

손님에게 거슬러줘야 하는 금액 money가 solution 함수의 매개변수로 주어집니다.

• money는 10 이상 100,000 이하의 자연수입니다.
• money는 10의 배수로만 주어집니다.

---

return 값 설명

거슬러 주는 동전과 지폐 개수합의 최솟값을 return 해주세요.

---

예시

money	return
2760	7

예시 설명

2760원을 거슬러주는 방법은 여러 가지가 있지만, 다음과 같이 거슬러 줄 때, 필요한 동전과 지폐 개수가 최소가 됩니다.

• 1,000원 : 2장
• 500원 : 1개
• 100원 : 2개
• 50원 : 1개
• 10원 : 1개

따라서 7을 return 하면 됩니다.

주어진 문제 7) 코드

def solution(money):
    coin = [10, 50, 100, 500, 1000, 5000, 10000, 50000]
    counter = 0
    idx = len(coin) - 1
    while money:
        counter += @@@
        money %= @@@
        idx -= @@@
    return counter

#아래는 테스트케이스 출력을 해보기 위한 코드입니다.
money = 2760
ret = solution(money)


#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은", ret, "입니다.")

Solution

주어진 문제 7) Solution 코드

이번에는 빈칸 채우기 문제이다.

def solution(money):
    coin = [10, 50, 100, 500, 1000, 5000, 10000, 50000]
    counter = 0
    idx = len(coin) - 1 # coin의 가장 큰 수 부터 차례로 거스름돈을 계산
    while money:
        counter += (money // coin[idx]) # (1)
        money %= coin[idx] # (2)
        idx -= 1 # (3)
    return counter

#아래는 테스트케이스 출력을 해보기 위한 코드입니다.
money = 2760
ret = solution(money)


#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은", ret, "입니다.")

• coin 리스트에 저장되어 있는 마지막 항목 (가장 큰 단위 화폐)부터 가져와 매개 변수 money가 0이 되지 않는 동안 실행한다.
  • 1) money를 coin 리스트의 현재 가져온 항목 값으로 나눈 몫을 현재 선택한 단위의 화폐 개수를 집계하여 counter에 저장한다.
  • 2) moeny를 coin 리스트에서 현재 가져온 항목 값으로 나눈 나머지로 지정한다. → 현재 사용 중인 단위 화폐를 이용하여 거슬러줄 수 있는 금액을 계산하고 난 나머지 금액을 money로 다시 저장한다.
  • 3) 그 다음으로 큰 단위 화폐를 가져올 수 있도록 인덱스를 나타내는 변수 idx에서 1만큼 감소한다.

해당 문제는 탐욕 알고리즘 (Greedy Algorithm)의 대표적인 사례로 현재 금액에서 사용할 수 있는 최대 단위 화폐부터 시작하여 거슬러줘야 하는 금액에 대한 화폐의 개수를 집계하는 프로그램을 완성해야 한다.

거스름돈 동전 개수와 그리디 (Greedy) 알고리즘 💡

우선, 화폐 단위가 10원, 30원, 60원, 100원 이라면, 그리디 (Greedy) 알고리즘을 적용하면 100원 1개 + 10원 2개 = 총 3개로 정답을 찾을 수 있다.

해당 알고리즘의 문제점은 해가 최적의 해가 아닐 수 도 있다는 점이다.
60원 1개 = 총 2개로 최적의 해를 못찾을 수 있다.

그러므로, 그리디 (Greedy) 알고리즘은 최적의 결과를 찾는 것에 실패하였다.

보통, 이전 단위의 배수 이상이 되면 그리디 알고리즘으로 풀 수 있다.
만약, 풀 수 없다면 동적 계획법 (Dynamic Programming)을 사용하여 해결 가능하다.