[백준/BOJ] - 1932번 python 풀이 - DP

---

1.Key Point

 

경우의 수가 3가지로 나누어지는 문제이다.

1번째 case는 가장 좌측 case

- 가장 좌측 case는 좌측 배열의 값끼리 더해주면 된다.

 

2번째 case는 가장 우측 case

- 가장 우측 case는 우측 배열의 값끼리 더해주면 된다.

 

마지막 case는 이외의 경우이다.

- 바로 위(상위 행) 왼쪽이나 바로 위(상위 행) 중 max 값을 골라 본인 값과 더하는 과정을 거친다.

---

import sys
input = sys.stdin.readline
n = int(input())
dp = [list(map(int, input().split())) for _ in range(n)]

for i in range(1,n): #idx 1~4까지 idx 0은 값이 안 바뀌니까 무시
    for j in range(i+1): #if i==1, j=0,1
        if j==0: #가장 좌측
            dp[i][0] += dp[i-1][0]
        elif i==j: #가장 우측
            dp[i][-1] += dp[i-1][-1]
        else: #이외의 경우
            dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])
print(max(dp[-1])) #최하단 배열의 최댓값 구하기