[Python] 프로그래머스 정수 삼각형

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

def solution(triangle):
    n_layer = len(triangle)
    memory = [[0 for j in range(len(triangle[i]))] for i in range(n_layer)]


    for layer in range(n_layer-1, -1, -1):
        if layer == n_layer-1:
            for idx, node in enumerate(triangle[layer]):
                memory[layer][idx] = node
        else:
            for idx, node in enumerate(triangle[layer]):
                memory[layer][idx] = node + max(memory[layer+1][idx], memory[layer+1][idx+1])

    return memory[0][0]

• 메모이제이션으로 풀이했다. 삼각형의 밑바닥부터 시작해서 왼쪽과 오른쪽 노드 중 큰 값을 판별해서 자기 자신 값과 더한 후, 그 값을 메모리의 해당 인덱스에 저장했다. 그런 방식으로 풀면 memory[0][0]에는 정답이 들어가게 된다.
• 일단 트라이앵글의 모양이 이진트리와 유사한 것을 이용해서 문제를 분할해보려 했다. 왼쪽 삼각형에서 최대 합, 오른쪽 삼각형에서 최대합을 구한 뒤, 그 중에서 더 큰 값을 자기 자신과 더하는 방식으로 재귀적으로 풀 수 있을 것 같았다. 그 후 재귀적 풀이를 메모이제이션으로 변형했다.