def solution(triangle):
answer = 0
dp = []
level = 1
for i in range(len(triangle)):
line = [-1] * level
dp.append(line)
level += 1
dp[0][0] = triangle[0][0]
# 각 레벨별로 돌기
for l in range(1, len(triangle)):
if l == 1:
dp[l][0] = dp[0][0] + triangle[1][0]
dp[l][1] = dp[0][0] + triangle[1][1]
continue
# level 2부터는
for j in range(l + 1):
# 맨 왼쪽의 경우, 그대로 더해서 내려오기
if j == 0:
dp[l][j] = dp[l - 1][0] + triangle[l][j]
# 맨 오른쪽의 경우, 그대로 더해서 내려오기
elif j == l:
dp[l][j] = dp[l - 1][j - 1] + triangle[l][j]
# 그 외 경우(중간), 두 경우 중 더 큰 경우 골라 더해 내려오기
else:
dp[l][j] = max(dp[l - 1][j - 1], dp[l - 1][j]) + triangle[l][j]
# dp의 마지막 레벨 값의 최대값 리턴
answer = max(dp[len(triangle) - 1])
return answer