How to solve this Coin Change problem?

Revision en3, by Lance_HAOH, 2017-12-31 10:06:04

Hi. I am trying to solve this problem.

For convenience, I have replicated the problem statement below:

A person is on floor N of a building. He has to take the lift down to floor 0. To use the lift exactly once, one token is needed. This lift is special as it can only travel downwards for one of the following levels each time it is used:

1, 5, 10, 17, 50, 100, 500, 1000, 5000, 10000

For example, if the person is standing on floor 6, one way to reach floor 0 is to take the lift down 5 floors, then take the lift again to go down 1 more floor (6 - 5 - 1 = 0). 2 tokens are used in this case.

The objective is to find the minimum number of tokens that the person needs to use to reach floor 0 from a given floor N. For the above example, the answer is 2.

My analysis:

This problem looks exactly like the classical coin change problem where we want to find the minimum number of coins to make up a given value. The latter problem can be easily solved using DP or BFS (or maybe matrix exponentiation?). Applying the same methods on this problem could earn us the points for all except the last subtask where N ≤ 1e9.

Could someone please advise me on a solution that would solve this problem in its entirety?

Postscript

UPD: I managed to solve this problem (thank you misof for your clear and concise hint!).

My approach can be found here.

My accepted code
Tags #dunjudgeme, #coin-change, #dynamic-programming, #algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Lance_HAOH 2017-12-31 10:06:04 25
en2 English Lance_HAOH 2017-12-29 08:26:02 690 Tiny change: 'ise hint!)\n\nMy app' -> 'ise hint!).\n\nMy app'
en1 English Lance_HAOH 2017-12-28 14:01:14 1944 Initial revision (published)