[프로그래머스] Lv.3 정수 삼각형 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/43105
• DP(Dynamic Programming) 동적 프로그래밍 문제
• 삼각형의 꼭대기에서부터 바닥까지 값을 누적해나가고 바닥에 있는 값 중 가장 큰 값을 리턴

def solution(triangle):
    answer = 0

    for i in range(1, len(triangle)): # 꼭대기에서 한칸 밑 부터 시작
        for j in range(len(triangle[i])):
            if j == 0: # 가장 왼쪽 값이면 위 칸의 가장 왼쪽 값을 더한다.
                triangle[i][j] += triangle[i-1][j]
            elif j == len(triangle[i]) - 1: # 가장 오른쪽 값이면 위 칸의 가장 오른쪽 값을 더한다.
                triangle[i][j] += triangle[i-1][j-1]
            else: # 중간에 있는 값이면 위에 두 숫자 중 큰걸 더한다.
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j]) 

    answer = max(triangle[-1]) # 마지막 리스트에서 최대값

    return answer