정수 삼각형

풀이

 처음에는 완전 탐색도 고려해봤으나 문제의 입력조건 n(1<= n <= 500)에 따른 시간 복잡도(최대 2^500)가 너무 커서 DP로 접근을 틀었다. 삼각형의 제일 밑층에서 위로 올라가면서 둘 중에 큰 값을 누적시키는 것을 반복하면 맨 위에 있는 곳이 정답이 된다.

n = int(input())

tri = []
for i in range(n):
    tri.append(list(map(int, input().split())))

for i in range(n-2, -1, -1):
    for j in range(len(tri[i])):
        tri[i][j] = max(tri[i+1][j] + tri[i][j], tri[i+1][j+1] + tri[i][j])

print(tri[0][0])

시간복잡도 : O(n^2)