说明

**贪心算法**核心思想：每一步都做当前最好的选择，期望达到全局最优。 面额 1, 5, 10, 20, 50, 100（元）。找零 m 元，求**最少**硬币枚数。

输入格式

一行，整数 m（1 \le m \le 10^6）。

输出格式

一行，最少硬币数。

93

6

提示

coins = [100, 50, 20, 10, 5, 1] cnt = 0 for c in coins: cnt += m // c m %= c print(cnt) 思考：如果面额是 1, 3, 4，找 6 元，贪心(4+1+1=3) vs 最优(3+3=2)，贪心会失效！