📌 [BOJ] 백준 1932 정수 삼각형

📖 문제

📖 예제

📖 풀이

import sys

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


for i in range(1, n):
  for j in range(i+1):
    if j == 0:
      dp[i][j] += dp[i-1][j]
    elif j == i:
      dp[i][j] += dp[i-1][j-1]
    else:
      dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])
      
print(max(dp[-1]))

본 문제의 점화식은 아래의 그림과 같다.
결과는 dp 행렬 마지막 행의 최대값을 출력하면 된다.