def solution(triangle):
    dp = []

    # 삼각형 아래에서부터 거꾸로 올라가면서 dp 계산
    for i, tri in enumerate(triangle[::-1]):
        if i == 0:
            dp.append(tri)
        else:
            dp.append([0] * len(tri))
            for j in range(len(tri)):
                dp[i][j] = max(tri[j] + dp[i - 1][j], tri[j] + dp[i - 1][j + 1])

    return dp[-1][0]



# 정확성  테스트
# 테스트 1 〉	통과 (0.02ms, 9.67MB)
# 테스트 2 〉	통과 (0.04ms, 9.65MB)
# 테스트 3 〉	통과 (0.08ms, 9.66MB)
# 테스트 4 〉	통과 (0.28ms, 9.77MB)
# 테스트 5 〉	통과 (1.53ms, 9.86MB)
# 테스트 6 〉	통과 (0.56ms, 9.7MB)
# 테스트 7 〉	통과 (1.74ms, 9.83MB)
# 테스트 8 〉	통과 (0.45ms, 9.63MB)
# 테스트 9 〉	통과 (0.02ms, 9.66MB)
# 테스트 10 〉	통과 (0.26ms, 9.77MB)

# 효율성  테스트
# 테스트 1 〉	통과 (37.50ms, 17.2MB)
# 테스트 2 〉	통과 (28.67ms, 15.6MB)
# 테스트 3 〉	통과 (44.28ms, 18.5MB)
# 테스트 4 〉	통과 (38.28ms, 17.3MB)
# 테스트 5 〉	통과 (35.36ms, 16.9MB)
# 테스트 6 〉	통과 (46.96ms, 18.5MB)
# 테스트 7 〉	통과 (41.96ms, 18MB)
# 테스트 8 〉	통과 (34.57ms, 16.5MB)
# 테스트 9 〉	통과 (35.08ms, 16.9MB)
# 테스트 10 〉	통과 (43.04ms, 18.2MB)