紙幣貨幣の枚数の合計が最小になるような払い方。

もっと良い書き方がある気がするけど、とりあえず作ってみたので。

作ったコード(Java)

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        long n = Long.parseLong(sc.next());

        LinkedHashMap<Integer, Long> map = countMoneyNum(n);

        // 結果表示
        for (Map.Entry<Integer, Long> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue() + "枚");
        }

    }

    // 紙幣貨幣の枚数を求める関数
    public static LinkedHashMap<Integer, Long> countMoneyNum(long n) {

        LinkedHashMap<Integer, Long> map = new LinkedHashMap<Integer, Long>();
        for (int unit : new int[] { 10000, 5000, 1000, 500, 100, 50, 10, 5, 1 }) {
            long a = n / unit;
            if (a != 0) {
                map.put(unit, a);
            }
            n = n % unit;
        }
        return map;
    }
}

上記コードの実行結果

例：「42195」を入力した場合

42195
10000 : 4枚
1000 : 2枚
100 : 1枚
50 : 1枚
10 : 4枚
5 : 1枚

例：「16666」を入力した場合

16666
10000 : 1枚
5000 : 1枚
1000 : 1枚
500 : 1枚
100 : 1枚
50 : 1枚
10 : 1枚
5 : 1枚
1 : 1枚

注意点

LinkedHashMap（putした順序を覚えてくれているHashMap）を使っているので、
10000→5000→1000→500→100→50→10→5→1
の順に出力される。出力順を変えたいときや2000円札を考慮したいときは改変が必要。
また、バリデーションっぽいことを何もしていないので、入力がおかしいとき（Long型におさらまない値とか「1以上の自然数」ではない値とか）の動作は保証しない。

おしまい。