[프로그래머스 Lv.3] 정수 삼각형 (Python)

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

프로그래머스

풀이

삼각형 꼭대기부터 최하단까지 내려가면서 거쳐간 수의 합이 최대인 경우를 뽑아내는 문제이다. DP를 사용해서 각 층에서의 최댓값을 저장하며 내려오는 하향식 방법으로 풀이해도 되고, 같은 방식으로 진행하되 상향식으로 가장 아래층부터 각 층의 최댓값을 저장하는 방식으로 풀이해도 된다. 하향식에 비해 코드가 더 간단하게 나오는 상향식으로 풀이해 보았다.

def solution(triangle):
    for i in range(len(triangle) - 2, -1, -1): # 밑에서 두번째 층부터, 제일 윗층(인덱스 0)까지 반복
        for j in range(len(triangle[i])): # 현재 층의 숫자를 순회
            cur = triangle[i][j] # 현재 층의 현재 위치의 숫자
            left = triangle[i+1][j] # 다음 층의 같은 인덱스에 있는 숫자는 그림 상의 왼쪽 아래 숫자 
            right = triangle[i+1][j+1] # 다음 층의 다음 인덱스에 있는 숫자는 그림 상의 오른쪽 아래 숫자
            triangle[i][j] = max((cur + left), (cur + right)) # 왼쪽 아래 숫자랑 더한 것이랑 오른쪽 아래 숫자랑 더한 것의 최대값은 현재 층에서 현재 위치까지 얻을 수 있는 최대값
    return triangle[0][0] # 가장 윗층은 가장 아래 층부터 모든 층을 하나씩 거쳤을 때 합의 최대값