그리디 알고리즘 이론

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로, 탐욕법이라고도 한다. 그리디 알고리즘을 이용할 때는 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다. 

• 코드업(CodeUp) 3301: 거스름돈
  문제설명
  어떤 가게의 욕심쟁이 점원은 거스름돈을 나눠줄때 거스름돈의 개수를 적게해서 주고자 한다.
  거스름돈을 입력 받아 점원이 줄 수 있는 최소 거스름돈의 개수를 출력하시오.
  예를 들어 54520원인 경우, 거스름돈으로 50000원권 1장, 1000원권 4장, 500원 1개, 10원 2개 해서 총 8개이다.
  (※ 현재 우리나라가 사용하고 있는 화폐를 사용한다. 10원 50원 100원 500원 1,000원 5,000원 10,000원 50,000원)

입력

거스름돈 n이 입력된다. (n은 10이상의 int 범위)

출력

최소 거스름돈의 개수를 출력한다.

입력 예시

54520

출력 예시

8

 

풀이

return_money = int(input()) # 거스름돈 입력받기
money_list = [50000, 10000, 5000, 1000, 500, 100, 50,  10] # 우리나라 화폐 리스트
result = 0 # 출력할 결과값 초기화
for money in money_list:
  result += return_money // money # 큰 수부터 몫을 계산
  return_money %= money # 거스름돈에 남은 거스름돈을 저장하고 반복하기
print(result) # 결과값 출력

이 문제에서는 큰 단위의 돈이 항상 작은 단위 돈의 배수이기 때문에 큰 단위의 돈을 주는 횟수가 작은 단위의 돈을 주는 횟수보다 항상 적다. 따라서 당장 줄 수 있는 가장 큰 단위의 돈부터 주면 최소 거스름돈의 개수를 구할 수 있다. 위와 같이 화폐리스트를 가장 큰 값부터 넣음으로써 가장 큰 단위의 돈부터 차례로 줄 수 있다.