신비로운 마을 코인홀트에서, 빵집 카운터 뒤에 서서 갓 구운 페이스트리를 정리하고 있어요. 문이 삐걱 열리더니, 좋은 물건을 알아보는 안목이 뛰어난 상인 데나라가 걸어 들어와요. 간단히 식사를 마친 데나라는 반짝이는 동전 하나를 카운터 위로 밀어요. 그 동전은 100단위의 가치를 지니고 있죠.
동전을 받으며 미소 짓고는, 식사값 총액을 흘낏 봐요: 88단위예요. 그렇다면 거스름돈으로 12단위를 돌려줘야 해요.
데나라가 기대에 찬 듯 손을 내밀어요. "동전은 가장 적게 주세요. 제 주머니는 이미 꽉 찼고, 가는 길에 잃어버릴까 봐 걱정되거든요." 하며 미소 지어요.
몇 가지 선택지가 있다는 걸 알고 있어요. "거스름돈으로는 Lumis(10단위 상당), Viras(5단위 상당), Zenth(2단위 상당) 세 가지가 있어요."
머릿속으로 재빨리 가능한 조합을 계산해 봐요:
"가장 좋은 선택은 동전 두 개예요: Lumis 하나와 Zenth 하나죠." 하며 거스름돈을 건네줘요.
데나라는 감탄한 기색이 역력하게 미소 지어요. "늘 그렇듯이, 정확하시네요."
손님에게 줄 동전의 값 합계가 정확한 거스름돈 금액과 같아지도록, 필요한 동전의 수를 가장 적게 구해요.
[1, 5, 10, 25, 100]이라면, 값이 5인 동전 한 개와 값이 10인 동전 한 개, 즉 [5, 10]을 반환해야 해요.[1, 5, 10, 25, 100]이라면, 값이 5인 동전 한 개, 값이 10인 동전 한 개, 값이 25인 동전 한 개, 즉 [5, 10, 25]를 반환해야 해요.Exercism에 가입하고 Go 트랙을 개념 34개연습 문제 165개, 그리고 실제 사람의 멘토링과 함께 배우고 익혀 보세요. 모두 무료예요.