문제
A cashier gives change using quarters (25¢), dimes (10¢), nickels (5¢) and pennies (1¢). Always using the largest coin that still fits gives the fewest coins for these values. Return how many coins are needed for cents.
Implement fewest_coins(cents).
Input
cents: The change owed in cents.
Output
Return the minimum number of coins.
제약 조건
0 ≤ cents ≤ 1,000,000
예시
예시 1
입력:
cents = 41
예상 출력:
expected = 4입력:
long long cents = 41;
예상 출력:
long long expected = 4;입력:
long cents = 41;
예상 출력:
long expected = 4;설명
One quarter (25), one dime (35), one nickel (40) and one penny (41): 4 coins.
예시 2
입력:
cents = 0
예상 출력:
expected = 0입력:
long long cents = 0;
예상 출력:
long long expected = 0;입력:
long cents = 0;
예상 출력:
long expected = 0;설명
No change is owed: 0 coins.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
가장 큰 동전부터 가능한 만큼 쓰고, 남은 금액으로 더 작은 동전으로 내려가세요.
힌트 2
나눗셈과 나머지를 이용해 각 동전 개수를 효율적으로 세세요.
힌트 3
정확히 나누어떨어질 때 남은 금액을 잘못 남기지 않도록 주의하세요.
예상 복잡도
시간 O(1), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.