프로그래머스. 정수 삼각형 파이썬 풀이

프로그래머스. DP. Level 3. 정수 삼각형 파이썬 풀이

문제링크 https://programmers.co.kr/learn/courses/30/lessons/43105

아래 그림처럼 빨간색으로만 경로가 이어진다.
그러므로 제일 왼쪽의 수는 자신의 오른쪽 위의 숫자에서만 길이 이어지고
제일 오른쪽의 수는 자신의 왼쪽 위의 숫자에서만 길이 이어진다
중간에 있는 수는 왼쪽 위, 오른쪽 위 둘 다 이어진다.

2번째 줄부터 마지막 줄까지 위의 알고리즘을 이용하여 더 큰 값을 더해가면 된다.

def solution(triangle):
    answer = 0
    
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j == len(triangle[i-1]):
                triangle[i][j] = triangle[i][j] + triangle[i-1][j-1]
            elif j == 0:
                triangle[i][j] = triangle[i][j] + triangle[i-1][j]
            else:
                triangle[i][j] = triangle[i][j] +  max(triangle[i-1][j-1], triangle[i-1][j])
        
    
    return max(triangle[-1])