거스름돈1 [알고리즘] #01 그리디 알고리즘-거스름돈 문제 # 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 # 주로 정렬 알고리즘과 함께 나오는 유형 🛠 거스름돈 문제 🔧 문제 카운터에는 거스름돈으로 줄 수 있는 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 🔧 아이디어 1) 거스름돈으로 줄 수 있는 단위 중 가장 큰 단위부터 돈을 거슬러준다. - 이 문제 상황에서는 500원부터 거슬러 줄 수 있는 최대한으로 거슬러 준다. - 1260원을 거슬러줘야 한다고 가정해보자. 화폐단위 500 100 50 10 손님이 받은 개수 2 0 0 0 - 500원을 최대한 많이 거슬러줬을 때, .. 2022. 5. 2. 이전 1 다음