Project Euler Problem 67

問題

By starting at the top of the triangle below and moving to adjacent numbers on the row
below, the maximum total from top to bottom is 23.

  [3]
 [7]5
 2[4]6
8 5[9]3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save
Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try
every route to solve this problem, as there are 2^99 altogether! If you could check
one trillion 10^12 routes every second it would take over twenty billion years
to check them all. There is an efficient algorithm to solve it. ;o)

Problem 17の100段バージョン！
全探索で探索したら200億年以上かかるんだって〜

入力
triangle.txt

ソース

File::open("triangle.txt") do |f|
	tri = f.readlines.map{|l| l.split(" ").map {|n| n.to_i}}

	(1...tri.size).each do |i|
		(0...tri[i].size).each do |j|
			max = 0
			max = tri[i - 1][j - 1] if j - 1 >= 0
			max = [max, tri[i - 1][j]].max if tri[i - 1].size > j
			tri[i][j] += max
		end
	end
	puts tri.last.max
end

解答

7273

感想

コピペのみ（汗
難なく終了！

追加

ファイル入力に変更