JOI 2007 予選 A おつり

qiita.com

続き。

atcoder.jp

コインの貪欲法の問題。

def main():
    n = 1000 - int(input())
    ans = 0
    while n > 0:
        for i in [500, 100, 50, 10, 5, 1]:
            if n >= i:
                n -= i
                ans += 1
                break
    print(ans)


if __name__ == '__main__':
    main()

これで通った。 次のやつもやってみたけど、貪欲法じゃないのでパス。