우리나라에서 현재 발행되고 있는 동전의 종류는 500원, 100원, 50원, 10원, 5원, 1원 의 6가지로 구성되어 있다.

성빈이는 설날 때 받은 세뱃돈으로 물건을 사려고 한다. 세배돈은 모두 만원짜리라서 가게에서 필요한 물건을 고른 후 만원짜리를 물건값에 맞도록 내고 거스름돈은 모두 동전으로 받으려고 한다. 주머니가 작은 관계로 가능하면 동전의 개수는 최소로 하고 싶다.

성빈이가 산 물건의 값을 입력받아 필요한 만원짜리가 몇장인지와 거스름돈의 최소 개수를 구하는 프로그램을 작성해 보자.

거스름돈 timer 1s memory 128MB

거스름돈 1s 128MB