Rich Person's Coin Exchange
Time limit2sMemory limit128 MB
Given a huge target amount M (up to 10^18) and up to 1000 coin denominations each at most 10000, find the minimum number of coins summing exactly to M.
- Level
Hard8 of 10
- Topics
- Shortest path, Graph, Dynamic programming, Math
- Solved
- No attempts yet
Problem
A person has an enormous amount of money. They want to exchange the entire amount into coins and store it.
The more coins there are, the harder they are to store, so they want to use the given coin denominations to make exactly the same amount with as few coins as possible. The amount must not decrease or increase by even 1 won.
Find the minimum number of coins needed to make exactly M won.
Input
The first line contains the amount M. (10^9 <= M <= 10^18)
The second line contains the number of coin denominations N. (1 <= N <= 1,000)
The third line contains N coin values A_i. (1 <= A_i <= 10,000)
A 1-won coin is always included among the denominations, so every amount can be made.
Output
Print the minimum number of coins needed to make exactly M won.