문제 출처 : https://www.acmicpc.net/problem/1932

---

문제 파악

dp문제임을 알고 풀었기에.. 바로 dp 점화식을 찾아보았다.

맨 위부터 아래로 내려오며 경로에 있는 수의 합을 출력하는데 가장 큰 합을 출력해야 한다.

1. 왼쪽 아래로 내려오거나, 2. 오른쪽 아래로 내려오거나

둘중 하나 인듯 보이지만 반례가 있다.

삼각형의 가장자리는 사실 그 숫자를 선택하는 경로가 두 갈래길이 아니라 한갈래길이다.

dp는 항상 dp[후] = dp[전] + someting 이라는 개념을 떠올리는 것이 중요한 것 같다.

dp[r][c] 는 r,c까지 도달할때까지의 최댓값을 저장해주는데

가장자리 의 경우에만 따로 처리해주는 로직을 구현하고
가운데 는 두가지의 경우로 처리하는 점화식을 세우면 될 듯 하다.

---

DP 테이블 초기화

dp테이블은 삼각형 배열과 동일하게 생겼는데 0으로 초기화되어야 한다.

# dp 테이블 0으로 초기화
dp = []
for i in range(n):
    row = []
    for j in range(i+1):
        row.append(0)
    dp.append(row)

2중 for문을 사용해 2차원 테이블인데 row들의 길이가 1씩 커지게 만들어주면 된다.

---

해답 및 풀이

import sys
input = sys.stdin.readline

# 입력 받기
n = int(input())

# 삼각형 2차원 배열에 저장
tri = []
for _ in range(n):
    tri.append(list(map(int,input().split())))

# dp 테이블 0으로 초기화
dp = []
for i in range(n):
    row = []
    for j in range(i+1):
        row.append(0)
    dp.append(row)

# 0,0까지 갈 수 있는 최댓값은 tri[0][0]의 값
dp[0][0] = tri[0][0]

# dp 가장자리
    # 왼쪽 가장자리 처리
for i in range(1,n):
    dp[i][0] = dp[i-1][0] + tri[i][0]    
    # 오른쪽 가장자리 처리 
for i in range(1,n):
    dp[i][i] = dp[i-1][i-1] + tri[i][i]   

# dp 가운데
for i in range(1,n):
    for j in range(1,i):
        dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + tri[i][j]

print(max(dp[n-1]))