[python]Dynamic Programming 동적계획법(dp) LG코테준비D-2 정수 삼각형

아래에서 위로 올라가기와 위에서 아래로 내려가기로 나누어서 두 가지 풀이로 풀어보자. 둘의 핵심 아이디어는 동일하다.
바로 현재 층에서 가능한 값들을 저장하며 최적의 경로를 계산하는 것이다.

1. 아래에서 위로 올라가기

def solution(triangle):
    floor = len(triangle) - 1

floor은 삼각형의 마지막 층이다. (index)

    while floor > 0:
        for i in range(floor):
            triangle[floor-1][i] += max(triangle[floor][i], triangle[floor][i+1])
        floor -= 1 

바닥에서 위층으로 올라간다. (N층부터 1층까지)
각 층의 모든 숫자를 탐색한다.
현재 칸에 아래칸의 두 숫자 중 큰 값을 더한다.
위층으로 이동한다.

    return triangle[0][0] 

2. 위에서 아래로 내려오기

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])): 
            if j == 0:
                triangle[i][j] += triangle[i-1][0]  # 위층의 첫 번째 값만 더하기
            elif j == len(triangle[i]) - 1:  # 오른쪽 끝인 경우
                triangle[i][j] += triangle[i-1][-1]  # 위층의 마지막 값만 더하기
            else:  # 그 외의 경우
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])  # 위층의 두 값 중 큰 값 더하기

    return max(triangle[-1])

두 번째 층부터 시작한다. 현재 층의 모든 숫자를 탐색한다. 왼쪽 끝인 경우는 j == 0이고 이 때는 위 층의 첫번째 값만 더한다.
오른쪽 끝인 경우는 j == len(triangle[i]) - 1이고 위층의 마지막 값만 더한다.
둘 다 아닐 경우에는 위층의 두 값 중 큰 값을 더한다.