정수 삼각형 ( 1932번 )

1932번: 정수 삼각형

 

나의 풀이

import sys

def _main(n, tree_list):
    for i in range(1, n):
        for j in range(len(tree_list[i])):
            if (j == 0):
                tree_list[i][j] = tree_list[i][j] + tree_list[i-1][0]
            elif (j == (len(tree_list[i]) - 1)):
                tree_list[i][j] = tree_list[i][j] + tree_list[i-1][-1]
            else:
                tree_list[i][j] = max(tree_list[i][j] + tree_list[i-1][j-1], tree_list[i][j] + tree_list[i-1][j])
    return max(tree_list[-1])

n = int(sys.stdin.readline())
tree_list = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
print(_main(n, tree_list))

 

시간 복잡도

for i in range(1, n): 트리를 돌며 최댓값을 산출 ( 이차형 시간 복잡도 )
    for j in range(len(tree_list[i])):
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )