https://www.acmicpc.net/problem/1932
1932번: 정수 삼각형첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.www.acmicpc.net
처음보는 구조라 당황했는데 dp개념만 알면 간단하다
좀만 들여다보면 규칙이 나온다
점화식
dp[i][j]=
j가 0이라면: dp[i][j]+=dp[i-1][j]
j가 마지막수라면 : dp[i][j] += dp[i-1][j-1]
else: dp[i][j] += max(dp[i-1][j-1]. dp[i-1][j])
마지막에 최댓값만 구해주면 된다
n=int(input())dp=[[* map(int,input().split())] for _ in range(n)]
for i in range(1,len(dp)): for j in range(len(dp[i])): if j==0:
dp[i][j]+=dp[i-1][j] elif j==len(dp[i])-1:
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[n-1]))