def solution(triangle):
    n = len(triangle);
    table = [[0] * n for j in range(n)];
    
    # root 값
    table[0][0] = triangle[0][0];
    
    for i in range(1, n):
        for j in range(i + 1):
            if j == 0:
                table[i][j] = table[i-1][j] + triangle[i][j];
            elif i == j:
                table[i][j] = table[i-1][j-1] + triangle[i][j];
            else:
                table[i][j] = max(table[i-1][j-1], table[i-1][j]) + triangle[i][j];
    return max(table[n-1])