Project Euler : Problem 18 『Maximum path sum I』

Stock Price / Dick Thomas Johnson

問題

　説明が難しいからProject Eulerのサイトで問題を見てもらったほうが早い。多分。
頂点から出発して近傍の数を足していき、一番下まで行ったときに最も大きくなる数は何か。
っていう問題になるのかな……。
英語をふんわりとしか理解してないから説明が難しい。

「英語はぜんぜんわからない。俺たちは雰囲気でProject Eulerを解いている」*1

メモ用の配列を使おうと思った

　ややこしくなったのでやめた。

全パターンを調べずに最大値を得る方法

　テスト用のコレ↓を使って説明する。
3
7 4
2 4 6
8 5 9 3

　まず最下段4段目と3段目を見る
2 4 6
8 5 9 3
　3段目6の近傍は9と3。
足して大きい方の数を6と置換する。
2 4 15
8 5 9 3
　次に3段目4の近傍は5と9。同じく足して大きい方の数を4と置換。
2 13 15
8 5 9 3
　そして最後に3段目2の近傍は8と5。足して大きい数は10。
10 13 15
8 5 9 3
　あとは同じことを3-2段、2-1段と繰り返し、最後に得る1段目の数が最大数になる。
とりあえず最後までやってみる。

　2段目と3段目から4の近傍は13と15。
7 4
10 13 15
　置き換える。
7 19
10 13 15
　7の近傍は10と13。なので7を20に置き換える。
20 19
10 13 15

　1段目と2段目。
3
20 19
　3の近傍の和で大きいのは23。
23
20 19

　1段目まで計算が終了したので、最大の数は23だと判明。
どんなに段数が大きくなろうが、構造が同じなら同じ手法が使える。
狐につままれたみたいな感じを受ける人は、ノートに書いて手でやると分かりやすい。

コード

using System;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace Problem18
{
    class Program
    {
        static void Main(string[] args)
        {
            int[][] data = FormatData(ReadFile());

            Debug.WriteLine(Maximum(data));
        }

        /// <summary>
        /// データを読み込む
        /// </summary>
        static string[] ReadFile()
        {
            string path = @"..\..\data.txt";

            return File.ReadLines(path).ToArray<string>();
        }

        /// <summary>
        /// テキストデータを数値に変換する
        /// </summary>
        static int[][] FormatData(String[] str)
        {
            int[][] data = new int[str.Length][];

            for (int i = 0; i < str.Length; i++)
            {
                String[] s = str[i].Split(' ');
                data[i] = new int[s.Length];

                for (int j = 0; j < s.Length; j++)
                {
                    data[i][j] = int.Parse(s[j]);
                }
            }

            return data;
        }

        /// <summary>
        /// 最大値を調べる
        /// </summary>
        static int Maximum(int[][] data)
        {

            for (int i = data.Count() - 2; i >= 0; i--)
            {
                for (int j = data[i].Length - 1; j >= 0; j--)
                {
                    int a = data[i][j] + data[i + 1][j + 1];
                    int b = data[i][j] + data[i + 1][j];

                    data[i][j] = (a >= b) ? a : b;
                }
            }

            return data[0][0];
        }
    }
}