C#でプロジェクトオイラーを解く（問題１８「最大経路の和 その1」）

Tweet

Pocket

どーも、みつおです。

総当たりで解く方法で実装した。

問題

以下の三角形の頂点から下まで移動するとき, その数値の和の最大値は23になる.

3
7 4
2 4 6
8 5 9 3

この例では 3 + 7 + 4 + 9 = 23.

以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

注: ここではたかだか 16384 通りのルートしかないので, すべてのパターンを試すこともできる. Problem 67 は同じ問題だが100行あるので, 総当りでは解けない. もっと賢い方法が必要である.

出典：Problem18

解答

読み込みデータは「data.txt」を参照してね。

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

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

        private static long Solve()
        {
            long ret = 0;

            //ファイルを読み込み
            List<string> data = ReadFile(@"C:\Work\プロジェクトオイラー\問題18\data.txt");

            //数値に変換したリストを作成
            List<List<long>> lines = ConvertData(data);

            //頂点から最下点までたどった最大値を取得
            ret = MaxNum(lines);

            return ret;
        }

        private static List<string> ReadFile(string filepath)
        {
            List<string> ret = new List<string>();

            //読み込みファイルを開く
            using (StreamReader file = new StreamReader(filepath))
            {
                string line = "";

                //最終行が空になるまで読み込み
                while ((line = file.ReadLine()) != null)
                {
                    //データを格納
                    ret.Add(line);
                }
            }

            return ret;
        }

        private static List<List<long>> ConvertData(List<string> data)
        {
            List<List<long>> ret = new List<List<long>>();

            //最終行までループ
            foreach (var tmp in data)
            {
                List<long> linedata = new List<long>();

                //行データを空白で分割
                string[] tmp_line = tmp.Split(' ');

                //列のループ
                for (int i = 0; i < tmp_line.Count(); i++)
                {
                    //数値に変換し、データを格納
                    linedata.Add(Convert.ToInt64(tmp_line[i]));
                }

                //行データを格納
                ret.Add(linedata);
            }

            return ret;
        }

        static long MaxNum(List<List<long>> data)
        {
            long ret = 0;
            List<long> num = new List<long>();

            //配列に変換
            var datanum = data.ToArray();

            //頂点を取得
            num.Add(datanum[0][0]);

            //行数分ループ
            for (int i = 1; i < datanum.Count(); i++)
            {
                //一番右の合計を取得
                long tmp = num[i - 1];

                //配列に変換
                var arraylist = num.ToArray();

                //列数分ループ
                for (int j = 1; j < num.Count(); j++)
                {
                    //左のデータを取得
                    long a = arraylist[j - 1];

                    //右のデータを取得
                    long b = arraylist[j];

                    //数値が大きくなる方に足しこむ
                    if (a > b) num[j] = a + datanum[i][j];
                    else num[j] = b + datanum[i][j];
                }

                //一番左側の合計値
                num[0] = num[0] + datanum[i][0];

                //一番右側の合計値
                num.Add(tmp + datanum[i][datanum[i].Count - 1]);
            }

            //最大値を取得
            ret = num.Max();

            return ret;
        }
    }
}

出力

1074