【Project Euler】Problem 18: 経路の合計の最大値 （その１）

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 18. 経路の合計の最大値 （その１）

問題の原文 Problem 18: Maximum path sum

問題の要約：上から下まで数字をたどった経路の合計の最大値を求めよ

一番下の行から順に値の大きい方を足して行くことによって最後に最大値が求まります。この例題の場合の推移を表のステップ#1-3で示します。

	ステップ1	ステップ2	ステップ3
3	3	3	23
7  4	7  4	20 19	20 19
2  4  6	10 13 15	10 13 15	10 13 15
8  5  9  3	8  5  9  3	8  5  9  3	8  5  9  3

プログラムにすると以下のようになります。三角形の配列triarrを作るコードは長いので下に載せました。

for y in range(len(triarr)-2,-1,-1):
  for x in range(y+1):
    triarr[y][x] += max(triarr[y+1][x],triarr[y+1][x+1])
print(f"Answer: {triarr[0][0]}")

import numpy as np

s = "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 "
N = 15
nums = s.split()
triarr, top = [], 0
for i in range(N):
  top += i 
  triarr.append(list(map(int,nums[top:top+i+1])))