[백준] 1932 정수 삼각형

📖 문제

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

💻 내 코드

import sys
n=int(sys.stdin.readline())
tri=[[0]]

for i in range(1, n+1):
    tri.append([0]+list(map(int, sys.stdin.readline().split())))

dp=[[0]*(n+1) for _ in range(n+1)]
dp[1][1]=tri[1][1]
for i in range(2, n+1):
    for j in range(1, len(tri[i])):
        dp[i][j]=max(dp[i-1][j-1], dp[i-1][j])+tri[i][j]

print(max(dp[n]))

💡 풀이

• 배열로 표현했을 때 현재 위치에서 삼각형의 대각선 왼쪽 위의 숫자는 배열에서 왼쪽 위의 숫자이고 삼각형의 오른쪽 위의 숫자는 바로 위의 숫자이다
• 따라서 dp[i][j]는 직전까지의 합이 들어있는 dp리스트에서 dp[i-1][j-1]과 dp[i-1][j]의 최대 값에 현재 수를 더한 값이다
• dp의 마지막행에 나온 수 들 중 최대 값을 찾으면 그 값이 가장 최대가 된다