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

문제를 정리해보자.

 

 

 

 

위와 같은 삼각형이 있다. 꼭대기에서 바닥까지 이어지는 경로 중,

거쳐간 숫자의 합이 가장 큰 경우를 찾으면 된다.

 

이동할 때는 대각선 방향으로 한 칸 왼쪽 또는 오른쪽으로만 이동할 수 있다.

예) 3에서는 8또는 1로만 이동할 수 있다.

 

 

 

 

 

풀이를 생각해보자.

 

거쳐 간 숫자의 합이 가장 크도록 그렸다. 

 

 

 

 

사진을 보면 알 수 있다. 대각선의 값은 현재 수의 누적값 + 다음 수이다. 

다음 수를 기준으로 왼쪽 대각선에서 오는 값과 오른쪽 대각선에서 오는 값 중 큰 값이 다음 수의 누적값이 된다.

 

예) 1은 왼쪽 대각선에서 오는 값이 11, 오른쪽 대각선에서 오는 값이 16이다.

따라서 16을 선택한다. 이것은 1의 누적값이 된다.

(구현할 때는 왼쪽 값을 먼저 저장하고, 오른쪽 값이 왔을 때 오른쪽 값이 더 크다면 오른쪽 값을 저장했다.)

 

 

점화식으로 작성해보자.

 

 

 

 

다음 수의 왼쪽 누적값 =  max(다음 수의 왼쪽 누적값, 현재 수의 누적값 + 다음 수)

다음 수의 오른쪽 누적값 = max(다음 수의 오른쪽 누적값, 현재 수의 누적값 + 다음 수)

 

 

 

구현해보자.

 

 

def solution(triangle):
    dp = [[0] * len(triangle_li) for triangle_li in triangle]
    dp[0][0] = triangle[0][0]  # 꼭대기

    for i in range(len(triangle) - 1):
        for j in range(len(triangle[i])):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + triangle[i+1][j])  # 왼쪽
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + triangle[i+1][j+1])  # 오른쪽

    return max(dp[-1])


solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]])