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

문제

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

풀이

DP

cache를 사용하지 않았을 때는 시간 초과가 발생합니다.

코드

cache = None
def solution(triangle):
    global cache
    cache = [[-1] * len(triangle[-1]) for _ in range(len(triangle))]
    answer = solve(0,0,len(triangle),triangle)
    return answer

def solve(x,y,n,triangle):
    global cache
    if y == len(triangle[x]): return -1
    elif x == n-1:
        return triangle[x][y]
    elif cache[x][y] != -1:
        return cache[x][y]
    
    a = solve(x+1,y,n,triangle)
    b = solve(x+1,y+1,n,triangle)
    
    cache[x][y] = triangle[x][y] + max(a,b)
    return cache[x][y]