[python.v파이썬] 백준 1932 정수 삼각형

[문제 출처]

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

1932번: 정수 삼각형

 

[소스 코드]

삼각형의 변에 해당하는 숫자는 이동할 수 있는 경로가 바로 위에 줄에 변에 해당하는 숫자밖에 없다.

따라서 양끝에 해당하는 숫자에 대해서는 윗 줄의 값을 더해준다.

가운데에 위치한 숫자의 경우 대각선으로 좌우가 가능하다.

인덱스로 따지면 행 인덱스는 하나 적고, 열 인덱스는 같거나 하나 적은 부분의 숫자에 해당한다. 

이 두 숫자 중에 더 큰 숫자를 더해서 저장한다.

#1932
n = int(input())
dp = []

for i in range(n):
  dp.append(list(map(int, input().split())))

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

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

print(max(dp[n-1]))