문제 설명
어떤 금액이 입력될 경우 그 금액을 지불하기 위해 필요한 최소 갯수의 지폐 갯수와 동전 갯수를 계산하는 프로그램을 작성하시오.
해당 금액을 지불하기 위해 사용할 수 있는 지폐의 종류는 10,000원, 5,000원, 1,000원의 3가지이고, 사용할 수 있는 동전의 종류는 500원, 100원의 2가지이다.
입력 설명
첫 번쨰 줄에 테스트케이스의 수 T가 입력된다.(1 <= T <= 10)
그 다음 줄부터 지불을 위한 금액(amount)이 정수로 T줄 만큼 입력된다(0 <= amount <= 10,000,000).
출력 설명
각 테스트케이스 별로 입력된 금액을 지불하기 위한 3종류의 최소 지폐 갯수와 2종류의 최소 동전 갯수를 높은 단위의 금액부터 순서대로 출력 예의 형식처럼 한 줄에 하나씩 출력한다.
만약 5가지 종류의 화폐로 지불이 불가능한 금액이거나 하나도 지불할 필요가 없는 경우에는 Sorry 라고 출력한다.
BILL : 3 1 2, COIN : 1 1
Sorry