Q05 いまだに現金払い？

C#のソース

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

class Program
{
    struct JyoutaiDef
    {
        internal int CurrP;
        internal List<int> CoinList;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrP = 0;
        WillPush.CoinList = new List<int>();
        stk.Push(WillPush);

        int AnswerCnt = 0;
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Popped.CoinList.Sum() == 1000) {
                AnswerCnt++;
                Console.WriteLine("解{0}を発見", AnswerCnt);
                var wkEnum = Popped.CoinList.GroupBy(X => X).OrderBy(X => X.Key);
                foreach (var EachGroup in wkEnum) {
                    Console.Write("{0}円玉が{1}枚。", EachGroup.Key, EachGroup.Count());
                }
                Console.WriteLine();
                continue;
            }

            //枝切り
            if (Popped.CoinList.Count >= 15) continue;

            int[] CoinArr = { 10, 50, 100, 500 };
            for (int I = Popped.CurrP; I <= CoinArr.GetUpperBound(0); I++) {
                WillPush.CurrP = I;
                WillPush.CoinList = new List<int>(Popped.CoinList) { CoinArr[I] };

                //枝切り
                if (WillPush.CoinList.Sum() > 1000) continue;

                stk.Push(WillPush);
            }
        }
    }
}

実行結果

省略
解18を発見
10円玉が5枚。50円玉が7枚。100円玉が1枚。500円玉が1枚。
解19を発見
10円玉が5枚。50円玉が9枚。500円玉が1枚。
解20を発見
10円玉が10枚。100円玉が4枚。500円玉が1枚。

解説

深さ優先探索でナイーブに解いてます。