최소 동전 거스름돈 1

문제 설명

500원, 100원, 50원, 10원, 5원, 1원짜리 동전이 충분히 존재합니다. 이 동전들을 이용해 금액 change 원을 거슬러줄 때 필요한 최소 동전 개수를 구하려고 합니다.

거스름돈 change가 주어졌을 때, 필요한 최소 동전 개수를 반환하는 solution 함수를 작성하시오.

예를 들어, change가 1,370이라면 아래와 같은 조합으로 총 8개의 동전을 사용하여 거슬러 줄 수 있습니다. 그리고 이 때 사용한 8개가 거스름돈에 필요한 최소 동전 개수에 해당합니다.

500원 2개(1000원), 100원 3개(300원), 50원 1개(50원), 10원 2개(20원)

제한 사항

• change는 1 이상 10,000 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 아래와 같은 조합으로 최소한의 동전(8개)을 사용해 1370원을 만들 수 있습니다.
  • 500원 2개(1000원), 100원 3개(300원), 50원 1개(50원), 10원 2개(20원)

2번 테스트케이스 설명

• 아래와 같은 조합으로 최소한의 동전(12개)을 사용해 888원을 만들 수 있습니다.
  • 500원 1개(500원), 100원 3개(300원), 50원 1개(50원), 10원 3개(30원), 5원 1개(5원), 1원 3개(3원)

3번 테스트케이스 설명

• 아래와 같은 조합으로 최소한의 동전(1개)을 사용해 100원을 만들 수 있습니다.
  • 100원 1개(100원)