C#でプロジェクトオイラーを解く（問題３１「硬貨の和」）

Tweet

Pocket

どーも、みつおです。

日本の硬貨でも問題作ってほしいよね。ポンドじゃなくてペンスじゃなくて円！！！

問題

イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

以下の方法で£2を作ることが可能である．

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

これらの硬貨を使って£2を作る方法は何通りあるか?

出典：Problem31

解答

using System;

namespace Problem31
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static int Solve()
        {
            int ret = 0;
            int num = 200;

            //2ポンドのループ
            for (int coin200 = num; 0 <= coin200; coin200 -= 200)
            {
                //1ポンドのループ
                for (int coin100 = coin200; 0 <= coin100; coin100 -= 100)
                {
                    //50ペンスのループ
                    for (int coin50 = coin100; 0 <= coin50; coin50 -= 50)
                    {
                        //20ペンスのループ
                        for (int coin20 = coin50; 0 <= coin20; coin20 -= 20)
                        {
                            //10ペンスのループ
                            for (int coin10 = coin20; 0 <= coin10; coin10 -= 10)
                            {
                                //5ペンスのループ
                                for (int coin5 = coin10; 0 <= coin5; coin5 -= 5)
                                {
                                    //2ペンスのループ
                                    for (int coin2 = coin5; 0 <= coin2; coin2 -= 2)
                                    {
                                        //1ペンスのループ
                                        for (int coin1 = coin2; 0 <= coin1; coin1 -= 1)
                                        {
                                            //値が0になったときにカウントアップ
                                            if (coin1 == 0)
                                                ret++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

            return ret;
        }
    }
}

出力

73682