효율적인 환전
면접 대비시간 제한3초메모리 제한512 MB
지불 금액이 주어질 때, 양쪽에서 거스름돈을 주고받는 것을 허용하면서 10의 거듭제곱 동전으로 교환되는 동전 수의 최솟값을 구한다.
문제
당신은 최근 이상한 화폐를 사들이는 은행에 취직했다. 이곳에서는 온갖 종류의 이상한 화폐로 결제하고, 입금하거나 출금할 수 있다. 출근 첫날, 당신은 네이메헨 출신 고객을 돕게 된다. 네이메헨은 10의 거듭제곱, 즉 1, 10, 100, 1000 등의 값을 가진 거대한 동전으로 유명한 작고 별볼일 없는 나라다. 이 고객은 꽤 큰 금액을 결제하려 하고, 당신은 그 많은 동전을 금고까지 들고 왔다 갔다 할 일을 생각하니 벌써 지긋지긋하다.
그래서 당신은 먼저 방법을 궁리해 보기로 한다. 당신에게도 고객에게도 네이메헨 동전이 엄청나게 쌓여 있다(네이메헨 시민 대부분은 무척 힘이 세다). 이제 고객이 지불해야 할 금액을 정확히 맞추기 위해 양쪽에서 오가는 동전의 총 개수를 최소화하려고 한다.
예를 들어 고객이 83을 결제하려 할 때 환전하는 방법은 여러 가지다. 그중 세 가지는 이렇다.
- 방법 1. 고객이 10짜리 동전 8개와 1짜리 동전 3개를 낸다. 동전 8 + 3 = 11개를 주고받아야 한다.
- 방법 2. 고객이 100짜리 동전 1개를 내고, 당신이 10짜리 동전 1개와 1짜리 동전 7개를 돌려준다. 동전 1 + 1 + 7 = 9개를 주고받아야 한다.
- 방법 3. 고객이 100짜리 동전 1개와 1짜리 동전 3개를 낸다. 당신이 10짜리 동전 2개를 돌려준다. 동전 1 + 3 + 2 = 6개를 주고받아야 한다.
마지막 방법이 가능한 한 동전을 적게 쓴다는 것을 알 수 있다.
입력
- 고객이 지불해야 할 금액을 나타내는 정수 하나가 주어진다.
출력
- 요구된 결제를 하기 위해 주고받아야 하는 동전 개수의 최솟값을 출력한다.