C++에서 총 금액을 지불하는 데 필요한 최소 코인 수 알아보기

숫자 N이 있고 1, 10 및 25 통화 동전의 가치가 있는 무제한 동전이 있다고 가정합니다. 정확한 금액 N을 지불하기 위해 사용해야 하는 최소 코인 수를 구합니다. N이 14라고 가정하면 코인의 수는 10가치 코인 1개와 1가치 코인 4개로 5가 됩니다.

이 문제를 해결하려면 다음 단계를 사용해야 합니다.

• N <10이면 N개의 1 가치 동전을 반환합니다.
• N> 9, N <25인 경우 값을 10으로 나누어 결과를 얻고 나머지는 1개의 가치 코인으로 덮고 개수를 추가하여 결과를 얻습니다.
• N> 25이면 25로 나누고 결과를 취하고 결과가 <25이면 두 번째 점에 대해 동일한 작업을 다시 수행합니다.

예시

#include<iostream>
using namespace std;
int countMinCoins(int n) {
   if(n<10)
      return n;
   else if(n > 9 && n < 25){
      int count = n/10;
      count += n%10;
      return count;
   } else {
      int count = n/25;
      return count + countMinCoins(n%25);
   }
}
int main() {
   int n = 88;
   cout << "Minimum number of coins required: " << countMinCoins(n);
}

출력

Minimum number of coins required: 7