소소한 개발이야기

📄 거스름돈 [백준 5585번] 🔗 [전체 소스 코드] 🔗 [문제 풀러가기] 그리디 알고리즘의 기본적인? 문제 입니다. 문제의 조건을 살펴보면 거스름돈을 거슬러 줄 때 동전의 개수를 최소로 만들어야 합니다. 동전 개수를 최소로 만들려면 단위가 큰 동전의 개수가 많아야 합니다. 문제의 예시를 보면 설명을 해보겠습니다. 문제에서 내야 할 금액은 380엔 입니다. 그러면 거스름돈은 620엔을 거슬러 줘야 합니다. 먼저 가장 큰 금액인 500엔 1개를 사용해 120원을 남길 수 있습니다. 그 다음 100엔 1개를 사용해 20원을 남길 수 있습니다. 그 다음 50엔은 남은 금액보다 크기 때문에 사용할 수 없으며 10엔 2개로 남은 금액을 모두 거슬러 줄 수 있습니다. 따라서 최소 개수는 4개 입니다. 그리디 알고..