문제
https://school.programmers.co.kr/learn/courses/30/lessons/43105
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한사항
삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
풀이 해설
def solution(triangle):
n = len(triangle)
dp = [[0]*(i+1) for i in range(n)]
dp[0][0] = triangle[0][0]
for i in range(1, n):
for j in range(i+1):
if j == 0:
dp[i][j] = dp[i-1][j] + triangle[i][j]
elif i == j:
dp[i][j] = dp[i-1][j-1] + triangle[i][j]
else:
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
answer = max(dp[n-1])
return answer
동적 프로그래밍을 활용해서 문제를 해결하였다. 각 삼각형에서 이동할 때 얻을 수 있는 최댓값을 2차원 배열로 만들어 저장하는 방식이다.
그리고 각 배열의 값을 선택하는 방식은 3가지이다.
첫 번째는 (i행, 0열)에 위치해 있을 때다. 이 경우에는 i-1행 0열에서 밖에 타고 들어올 수 없기 때문에 해당 값에서 triangle의 해당 행, 열의 값을 더해주면 최댓값이 된다.
두 번째는 (i행, i열)에 위치해 있을 때다. i행 i열에 위치해 있다는 것은 해당 행의 가장 마지막 열에 위치해 있다는 것을 의미한다. 따라서 해당 (i-1)행과 (j-1)열에서만 이동이 가능하므로 해당 값에서 triangle의 해당 행, 열의 값을 더해주면 최댓값이 된다.
마지막은 그 외의 경우일 것이다. 삼각형의 이동경로는 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다고 되어있으므로 (i-1)행 (j-1)열 혹은, (i-1)행에서 j열에서 이동하는 경우가 있다. 이 중 최댓값을 선택해서 triangle의 해당 행, 열의 값을 더해주면 최댓값이 된다.
