[백준 1932 / Python] 정수 삼각형

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

dp 점화식을 구할 때 왼쪽, 오른쪽 대각선 중 더 큰 값을 구한다는 개념을 구하면 된다.
즉, dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j] 이다.

코드

n = int(input())    # 삼각형의 크기 입력
arr = [[0 for _ in range(n+1)] for _ in range(n+1)] # 삼각형 생성
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]   # dp 생성

# 삼각형에 수를 입력
for i in range(1, n+1):
    temp = list(map(int, input().split()))
    for j in range(1, i+1):
        arr[i][j] = temp[j-1]

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

print(max(dp[-1])

결과