문제

풀이

먼저 이문제는 dp를 어떻게 적용 해야하는가로부터 궁금증이 시작한다. dp테이블을 1차원 리스트가 아닌 2차원 리스트로 구현하겠다는 아이디어만 떠오르면 그때부터 는 간단하다.

점화식의 아이디어는 간단하다.
2차원 dp테이블인 d[i][j]가 의미하는 바는 i열의 j행에 를 마지막으로 더했을때 최대가되는 경로의 합을 의미하고
이에따라 점화식을 도출해보면 당연히

d[i][j] = max(d[i-1][left], d[i-1][right]) + 삼각형[i][j]가 된다

실제로 구현해 봤을 때는

d[i][j] = max(d[i-1][j-1], d[i-1][j]) + tri[i][j]

가된다.

이 풀이를 코드에 녹여보면 이렇다.

코드

#입력
#첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

#점화식
#dp[i][j] =  max(dp[i-1][j], dp[i-1][j-1]) + array[i][j+1])

import sys
N = int(sys.stdin.readline().rstrip())

tri = []
tri.append([int(sys.stdin.readline().rstrip())])

for i in range(1,N):
  tri.append(list(map(int, sys.stdin.readline().split())))

dp = [[0] * N for _ in range(N)]
dp[0][0] = tri[0][0]

#바텀업으로 dp테이블 채우기
for i in range(1, N):
  for j in range(0, i+1):
    #왼쪽일 때
    if(j == 0):
      dp[i][j] = dp[i-1][j] + tri[i][j]
    
    #오른쪽일 때
    elif(j == i):
      dp[i][j] = dp[i-1][j-1] + tri[i][j]

    else:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + tri[i][j]
      
print(max(dp[N-1]))