신비로운 마을 코인홀트에서, 빵집 카운터 뒤에 서서 갓 구운 페이스트리를 정리하고 있어요. 문이 삐걱 열리더니, 좋은 물건을 알아보는 안목이 뛰어난 상인 데나라가 걸어 들어와요. 간단히 식사를 마친 데나라는 반짝이는 동전 하나를 카운터 위로 밀어요. 그 동전은 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]를 반환해야 해요.| 레지스터 | 용도 | 타입 | 설명 |
|---|---|---|---|
$a0 |
입력 | 정수 | 입력 동전의 개수 |
$a1 |
입력 | 정수 | 목표 금액 |
$a2 |
입출력 | 주소 | 덮어쓸 수 있는 동전 워드 배열 |
$v0 |
출력 | 정수 | 출력 동전의 개수, 입력이 유효하지 않으면 -1 |
$t0-9 |
임시 | 아무 타입 | 임시 저장에 사용 |
Exercism에 가입하고 MIPS Assembly 트랙을 연습 문제 70개, 그리고 실제 사람의 멘토링과 함께 배우고 익혀 보세요. 모두 무료예요.