solution link:https://www.codechef.com/viewsolution/14156262
problem link:https://www.codechef.com/problems/COINS
what is wrong with the solution?
This is a basic dp question and here is my accepted solution
https://www.codechef.com/viewsolution/12741814
if you still have any doubt then feel free to comment
You are doing a basic error.
Lets say the coin value is X.
We see that X/2 +X/3+X/4 is greater than X. Good!
But we can further break that X/2 , X/3 and X/4 into even smaller pieces such that we get more coins.
Eg- lets take X=100
We get coin 50,33,25.
Now we can divide 50 to- 25, 16,12.
Similarly we can do to 33 and 25.
Meaning, you have to do the process on and on, until dividing into smaller coins yields no profit. (Maths will show that this for X<=12 , we get no profit)
What you will ahve to do is recursion +memonisation.
But how will you store the values? (As such large array isnt possible)
In C++, there is a data structure called maps. Its speciality is that, you can define the “key” by which you will access the element. So when you say map[x]=x, it will store x and make a key “x” to access it. (Do some research on it if needed)
OR
You can just store results for values <=10^7 or 10^8 in array and still happily solve the question. Get back to me if doubt exists.
2 Likes