blob: f8aabd3b4be19b07809d1a91e73f20c5b598e296 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
# Uses python3
import sys
def getChange(money):
denominations = [1, 3, 4]
minNumCoins = [0] * (money + 1)
for m in range(1, len(minNumCoins)):
minNumCoins[m] = float('inf')
for i in range(len(denominations)):
if m >= denominations[i]:
numCoins = minNumCoins[m - denominations[i]] + 1
if numCoins < minNumCoins[m]:
minNumCoins[m] = numCoins
return minNumCoins[money]
if __name__ == '__main__':
m = int(sys.stdin.read())
print(getChange(m))
|
