프로그래머스 - 정수 삼각형

정수 삼각형

설명

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

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

def solution(triangle):
    answer = 0
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:
                triangle[i][j] = triangle[i][j]+triangle[i-1][j]
                continue
            if j == len(triangle[i])-1:
                triangle[i][j] = triangle[i][j]+triangle[i-1][j-1]
                continue
            triangle[i][j] = max(triangle[i][j]+triangle[i-1][j-1], triangle[i][j]+triangle[i-1][j])
    # print(triangle[len(triangle)-1])
    answer = max(triangle[len(triangle)-1])
    return answer

• DP 유형의 문제들은 대체로 모든 경우 중 최대or최소를 찾는 느낌
• 이 문제도 모든 경우를 탐색하기에는 너무 많으니까 위에서부터 찾아내려오자

1. 가장 왼쪽 : 본인 값 + 본인의 우측 상단 값
2. 가장 오른쪽 : 본인 값 + 본인의 좌측 상단 값
3. 그 외 : 본인 값 + (좌측 상단 / 우측 상단 중 더 큰 값)

• 이 중 최대값을 계속 업데이트해가면서 마지막 줄까지 내려오자
• 그 중 최대값을 리턴하면 끝