Project Euler .NET のProblem 18について
結構悩んだ。暫く眺めていると三角形の底辺から順に値が大きくなるように値を覚えていけばよいことに気づいた。例えば三角形の左下の角辺りにある63という数字のある場所を経路とする場合,その下の右下の62という場所を必ず通る。この場所を63+62=125という数字のある場所と考えれば、下の2経路について考える必要は無くなる。同じように63という数字のある場所の隣の場所も66+98=164という数字のある場所と考えれば下の2経路について考える必要は無くなる。これを同じ列の全てに対して処理を行うと列が1段少なくなった三角形ができる。あとは同じように繰り返していくと段々列が無くなり、三角形の頂点のみが残る。そのときの値が最大値となる
以下ソースコード
List<List<int>> triangleList = new List<List<int>>();
// ファイルから数字を取り出している
using (StreamReader sr = new StreamReader("data2.txt")) {
string str = "";
while ((str = sr.ReadLine()) != null) {
IEnumerable<int> list = from element in str.Split(' ')
select int.Parse(element);
triangleList.Insert(0, list.ToList<int>()); // 三角形の最下段がリストの一番最初に来るようにしている
}
}
List<int> sumList = triangleList[0];
int downLeftNum, downRightNum;
int maxNum;
for (int i = 1; i < triangleList.Count; ++i) {
List<int> list = triangleList[i];
List<int> tmpSumList = new List<int>();
for (int j = 0; j < list.Count<int>(); ++j) {
downLeftNum = sumList.ElementAt<int>(j);
downRightNum = sumList.ElementAt<int>(j + 1);
maxNum = (downLeftNum >= downRightNum) ? downLeftNum + list.ElementAt<int>(j) : downRightNum + list.ElementAt<int>(j);
tmpSumList.Add(maxNum);
}
sumList = tmpSumList;
}
int maxVal = sumList.ElementAt<int>(0);
