[동적계획법] 프로그래머스 정수 삼각형

지난 번에 풀지 못한 삼각형 문제 관련하여 개인적으로 약한 동적 계획법과 깊이탐색 등의 부분이 나온 것 같아 관련 문제를 다시 풀어보고 있는 중이다.

 

관련해서 정수 삼각형 문제의 경우 동적 계획법에 해당되는 문제로 처음에 전혀 접근 방법을 찾지 못했던 문제이다.

 

관련 풀이는 https://velog.io/@younge/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A0%95%EC%88%98-%EC%82%BC%EA%B0%81%ED%98%95-%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95 를 참고하였다.

 

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