[백준/파이썬] 1932 정수 삼각형

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

---

알고리즘 분류

• 다이나믹프로그래밍

문제풀이

하나씩 적어가면서 규칙을 찾았다.
ex)
d[0][0]=7
d[1][0]=3+7, d[1][1]=8+7
d[2][0]=8+d[1][0], d[2][1]=1+max(d[1][0],d[1][1]),
d[2][2]=0+d[1][1]

d[3][0]=2+d[2][0], d[3][1]=7+max(d[2][0],d[2][1]),
d[3][2]=4+max(d[2][1],d[2][2]), d[3][3]=4+d[2][2]
...

각 라인의 처음과 끝은 바로 위에 숫자를 더해주면 되고,
나머지는 왼쪽 대각선, 오른쪽 대각선 중 최댓값을 더해나가 계속 누적시키면 된다.
7
3 8
->
7
10 15
->
7
10 15
18 16 15...

소스코드

n=int(input())
d=[]
for i in range(n):
  d.append(list(map(int, input().split())))

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