[BAEKJOON/Python3] 백준 5585 거스름돈

www.acmicpc.net/problem/5585

5585번: 거스름돈

＊링크로 접속하여 문제를 확인할 수 있습니다.

 

그리디 알고리즘의 가장 대표적인 문제가 아닐까 싶은 거스름돈 문제입니다. 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고 1000엔을 냈을 때 거스름돈의 개수를 가장 적게 할 때의 거스름돈 개수를 구하는 문제입니다.

 

간단하게 생각해서 거스름돈 종류에 따라 하나하나 나눠서 원하는 값이 거스름돈으로 나눠서 몫이 있다면 몫을 거스름돈 개수에 더하고 원하는 값은 그로 나눈 나머지가 남게 된다는 것을 이용하여 해결하였습니다. 그러나 처음에는 하나하나 if문을 사용해서 진행하였고 코드가 같은 부분이 반복되도록 길어져서 그 부분을 모두 for문으로 한번에 처리하도록 하였습니다.

 

코드

 

간단하게 for문을 이용한 코드입니다.

거스름돈을 줄 것이기 때문에 1000엔에서 구매한 가격을 빼고 각 거스름돈의 종류를 리스트로 만들어 반복문을 통해 몫이 있다면 몫을 개수에 더하고 그 나머지가 계속 같은 방법으로 이루어지도록 한 것입니다.

 

이 문제에서 핵심은 500엔짜리가 100엔짜리로 쪼개질 수 있는 등 큰 단위가 작은 단위들의 배수로 표현된다는 것입니다. 그렇기 때문에 500엔에서 안되면 100엔으로 넘기고 했을 때 최솟값을 구할 수 있는 것입니다. 만약 큰 단위가 작은 단위들의 배수로 표현될 수 없다면 최솟값을 이 방법으로 구하지 못할수도 있습니다.