문제

https://school.programmers.co.kr/learn/courses/30/lessons/43105

풀이

시도 1 index 에러를 없애기 위해 배열 앞뒤에 0을 추가후 top-down 으로 내려가면서 현재 배열 원소에 최대값을 더해주고 마지막 배열중 가장 최대값을 리턴합니다.

solution.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def solution(triangle):
    # index 에러 방지 위해 앞 뒤에 0인 원소를 추가합니다.
    triangle = [[0] + line + [0] for line in triangle]
    # print(triangle)
    # 맨앞은 0이니깐 1부터
    for i in range(1, len(triangle)):
        # 맨앞은 0이고 2씩 증가하여 가운데 수를 넘어뛰어도 됨
        for j in range(1, i+2):
            # 현재 원소 + 이전 인접하는 두개의 원소중 최대값을 더함
            triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
    # 마지막줄 원소중 최대값 리턴
    return max(triangle[-1])

s = solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]])
print(s)

다른사람풀이

solution.py 
1

solution = lambda t, l = []: max(l) if not t else solution(t[1:], [max(x,y)+z for x,y,z in zip([0]+l, l+[0], t[0])])