거스름돈 만들기

금액과 (거의) 무제한으로 쓸 수 있는 동전이 주어졌을 때(이 문제에서 지폐는 다루지 않는다), 어떤 금액은 여러 방법으로 만들 수 있다. 물건을 사고 값을 치를 때에는 거스름돈을 돌려받아야 할 수도 있어 문제가 더 흥미로워진다. 대부분의 지갑에는 동전이 한정된 개수만 들어 있으므로, 값을 치르기 위해 금액을 만드는 방법에도 제약이 있다.

우리의 목표는 이러한 거래에서 주고받는 동전의 총 개수를 최소로 만드는 것이다. 단, 상점 주인은 모든 종류의 동전을 충분히 가지고 있다고 가정한다. 사용할 수 있는 동전은 5c, 10c, 20c, 50c, $1, $2 여섯 종류다.

예를 들어 55c를 내야 하는데 50c 동전이 없다고 하자. 20c 두 개 + 10c + 5c로 내면 동전은 모두 4개다. 대신 $1을 내면 45c를 거슬러 받는데 이 역시 4개다. 그러나 $1.05($1 + 5c)를 내면 50c를 거슬러 받아, 주고받는 동전이 모두 3개뿐이다.

내가 가진 동전과 구매 금액을 읽어들여, 주고받는 동전의 최소 개수를 구하는 프로그램을 작성하라.

입력은 여러 줄로 이루어지며, 각 줄은 서로 다른 상황을 나타낸다. 각 줄에는 5c, 10c, 20c, 50c, $1, $2 순서로 내가 가진 동전의 개수를 나타내는 정수 6개가 오고, 이어서 거래 금액을 나타내는 실수가 온다. 이 금액은 항상 $5.00 미만이다. 입력은 여섯 개의 0(0 0 0 0 0 0)으로 이루어진 줄로 끝난다. 내가 가진 동전의 총액은 항상 금액을 치르기에 충분하며, 금액은 항상 만들 수 있다(항상 5c의 배수다).

입력의 각 상황마다 한 줄씩, 주고받는 동전의 최소 개수를 폭 3칸에 오른쪽 정렬하여 출력한다.