ABC208-B Factorial Yen Coin

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("9");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("119");
            //10
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10000000");
            //24
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long P = long.Parse(InputList[0]);

        var KaijyouDict = new Dictionary<long, long>();
        long KaijyouVal = 1;
        for (int I = 1; I <= 10; I++) {
            KaijyouVal *= I;
            KaijyouDict[I] = KaijyouVal;
        }

        long Rest = P;
        long Answer = 0;
        foreach (var EachPair in KaijyouDict.OrderByDescending(pX => pX.Value)) {
            // 100枚まで
            for (int I = 1; I <= 100; I++) {
                if (Rest >= EachPair.Value) {
                    Rest -= EachPair.Value;
                    Answer++;
                }
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

日本の硬貨は、1円,5円,10円,50円,100円,500円
がありますが、任意の金額に対して最小の枚数で
支払う場合は、大きい数から貪欲に枚数を決めていくのが最適です。

なぜなら、
1円と5円だけで考えると
5円は1円の倍数なので
5円を使って払えるだけ払うのが最適と分かります。

1円と5円と10円だけで考えると
10円は1円と5円の倍数なので
10円を使って払えるだけ払ってから
5円を使って払えるだけ払ってから
のが最適と分かります。

100円と500円が増えても同様となります。

同様の考えて、階乗であれば、倍数関係になるので
同じアルゴリズムが使えます。