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

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

프로그래머스

풀이

DP 문제이기에 문제 해결을 위한 규칙을 찾아서 점화식을 세우는 것이 가장 중요하다.

삼각형의 위에서부터 아래로 내려오면서 숫자를 더하여 각 위치에 들어갈 수 있는 최댓값을 얻어내고, 이를 저장하는 방식을 반복하여 삼각형을 모두 채운다. 가장 아래층에서의 최댓값이 구하고자 하는 답이 된다.

def solution(triangle): 
    _triangle = [] # 각 위치에서의 최대값을 저장할 배열
    for i in range(len(triangle)): # 정수 삼각형과 동일하게 배열 구조 저장
        _triangle.append([0 for _ in range(i+1)])
    
    _triangle[0] = triangle[0] # 가장 윗층은 그대로
    for i in range(1, len(triangle)): # 위에서 2번째 층부터 마지막 층까지
        for j in range(len(triangle[i])): # 층별로 모든 위치에서
            if j == 0: # 왼쪽 끝의 경우에는 윗층의 하나만 더할 수 있음
                _triangle[i][j] = triangle[i][j] + _triangle[i-1][j]
            elif j == len(triangle[i]) - 1: # 오른쪽 끝의 경우에도 윗층의 하나만 더할 수 있음
                _triangle[i][j] = triangle[i][j] + _triangle[i-1][j-1]
            else: # 그 외 경우에는 윗층의 양쪽 둘 모두 더할 수 있으므로 둘 중에 최댓값을 저장
                _triangle[i][j] = max(triangle[i][j] + _triangle[i-1][j], triangle[i][j] + _triangle[i-1][j-1])
        
    return max(_triangle[len(triangle)-1]) # 제일 아래층에서 최대값을 반환