BOJ 1932번: 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

dp를 통해 푸는 방법을 생각하는 것은 어렵지 않았다.

n=0, n=1인 경우는 초기값으로 두고 dp[i][j] = arr[i][j] + max(dp[i-1][j-1], dp[i-1][j]) 로 점화식을 생각했는데, 이렇게 하면 j = 0일 때 인덱스에러가 나기 때문에 dp를 [n][n+1] 로 설정하였다.

그 다음에는 n = 0, n = 1일때 예외처리를 하지않아서 인덱스에러가 나왔다..ㅎㅎ

 

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in  range(n):
    arr.append(list(map(int, input().split())))
    
if (n==1):
    print(arr[0][0])
    sys.exit(0)
    
elif (n==2):
    print(max(arr[1][0], arr[1][1])+arr[0][0])
    sys.exit(0)
    
dp = [[0]*(n+1) for _ in range(n)]

dp[0][1] = arr[0][0]
dp[1][1] = dp[0][1] + arr[1][0]
dp[1][2] = dp[0][1] + arr[1][1]

for i in range(2, n):
    for j in range(1,i+2):
        dp[i][j] = arr[i][j-1] + max(dp[i-1][j-1], dp[i-1][j])
   
print(max(dp[n-1]))