문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

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

제한사항

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

입출력 예

triangle												result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

접근 방법

이번 문제는 다이나믹 프로그래밍을 통하여 해결하였다. 우선 왼쪽 대각선과 아래쪽 대각선으로만 이동하는 것을 2차원 리스트에서의 좌표로 보면 왼쪽 대각선은 y축을 1 더하는 것과 같고, 오른쪽 대각선은 y, x축 모두 1 더하는 것과 같다. 각 줄에서의 첫 숫자와 마지막 숫자의 경우에는 한쪽에서만 수가 넘어오기 때문에 먼저 따로 관리를 해주었다.

dp[i][0]=dp[i-1][0]+triangle[i][0]
dp[i][-1]=dp[i-1][-1]+triangle[i][-1]

이 과정은 삼각형의 밑변을 제외한 두 변에 대한 메모라이제이션 과정이다. 그리고 안쪽에 남은 좌표들에 대해서는 다음과 같은 점화식으로 접근하였다.

dp[i][j]=max(dp[i-1][j], dp[i-1][j-1])+triangle[i][j]

수가 넘어올 수 있는 두가지 좌표의 dp 중 더 큰 값에 현재 위치의 값을 더하는 방식으로 현재 위치의 dp를 저장하였다.

마지막에는 dp[len(triangle)-1] 리스트에서의 최대값을 반환하도록 하였다.

• dp 리스트를 선언한다.
• dp[0][0]을 triangle[0][0]으로 갱신한다.
• 1부터 triangle의 길이까지 반복하는 i에 대한 for문을 돌린다.
  -> dp[i][0]을 dp[i-1][0]+triangle[i][0]로 갱신한다.
  -> dp[i][-1]을 dp[i-1][-1]+triangle[i][-1]으로 갱신한다.
• 2부터 triangle의 길이까지 반복하는 i에 대한 for문을 돌린다.
  -> 1부터 triangle의 길이-1까지 반복하는 j에 대한 for문을 돌린다.
  --> dp[i][j]를 dp[i-1][j]와 dp[i-1][j-1] 중 더 큰 값에 triangle[i][j]를 더한 값으로 갱신한다.
• dp[len(triangle)-1]에서의 최대값을 정답 변수 answer에 저장한다.
• answer를 반환한다.

solution.py

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