This is a question on Codeforces [ Problem - 996A - Codeforces].
I think this question can be solved using both GREEDY and DP but since I was practicing DP I tried it.
I just used basic DP minimum coin change problem approach and it’s working fine but on this testcase where n=1000000000, it’s crashing…
I tried to use long long but still anything works and things got worse…
Although I submitted the GREEDY approach I got an AC, I want to know why my DP approach doesn’t work…
Here’s my solution [aLWgZ6 - Online C++0x Compiler & Debugging Tool - Ideone.com] .