문제
이 문제를 처음 보자마자 dp로 풀어줘야겠구나 하는 생각이 들었다.(물론 문제에 아예 적혀있긴하다)
아무튼 dp를 어떤식으로 활용하여 풀어주는가 이게 관건인데 이전열에서 올 수 있는 값중 최댓값을 계속해서 더해가는 방식으로 처리해주면 된다.
이때 정수 삼각형을 배열로 작성하게 되면
[7]
[3,8]
[8,1,0]
[2,7,4,4]
[4,5,2,6,5]
이렇게 된다는것을 알 수 있다.
이때 행의 번호가 0인 것은 이전 열에서 행의 번호 0 인 것만 받을 수 있고
해당열의 가장 마지막 행은 이전 열의 가장 마지막 행만 받는다는 것을 알 수 있다.
그리고 이외의 부분은 [이전열][행의번호-1] 과 [이전열][행의번호동일] 이 두개의 인덱스에 해당하는 값중 최댓값이 되는 값을 받는다.
이를 코드로 정리하면
def solution(triangle):
answer = 0
n = len(triangle)
for i in range(1,n):
for j in range(0,len(triangle[i])):
# 첫번째 행 예외처리
if j == 0 :
triangle[i][j] += triangle[i-1][j]
#마지막 행 예외처리
if j == (len(triangle[i])-1):
triangle[i][j] += triangle[i-1][j-1]
#그외
if j != 0 and j != (len(triangle[i])-1) :
triangle[i][j] += max(triangle[i-1][j-1],triangle[i-1][j])
#누적된 값중 가장 큰 값을 출력
answer = max(triangle[n-1])
return answer이렇게 된다.
이 문제에서 dp를 사용하는 것은 맞지만 따로 dp 배열을 만들어주지는 않았고 기존에 있는 triangle 배열을 사용하여 해당 배열에 값을 갱신해주는 방식으로 값들을 저장해주었다.
