Minimum Number of Coins

Given a non-negative integer \(n\), the task is to determine the minimum number of coins required to make up the amount \(n\) using coins of denominations 1, 3, and 4. You can solve this problem using dynamic programming where the recurrence relation is given by:

\(dp[i] = \min\{ dp[i-1]+1,\; dp[i-3]+1,\; dp[i-4]+1 \}\)

It is guaranteed that a solution always exists for every non-negative \(n\). Read the input from stdin and output the answer to stdout.

inputFormat

The input consists of a single line containing an integer \(n\) (where \(0 \leq n \leq 10^6\)).

outputFormat

Output a single integer representing the minimum number of coins needed to sum up to \(n\).

6

2