[백준][python] 1932.정수삼각형 - DP

• 백준 1932.정수삼각형 Silver I
• 문제링크 

1932번: 정수 삼각형

나의 코드

이 문제 역시 동적계획법을 통해 풀었다. N개의 list가 주어지는데, 들어오는 list의 한 element마다 그 전의 list의 left, right value 중 더 큰 값을 더해주었다. 마지막 list에서 가장 큰 숫자를 리턴해주면 된다. Index out of range 에러가 뜨지 않기 위해 첫 번째 원소 값과 마지막 원소 값에 대한 조건 처리 역시 해주어야 한다.

import sys

N = int(sys.stdin.readline())
lsts = []

for i in range(N):
    lst = list(map(int, sys.stdin.readline().split()))
    lsts.append(lst)

    # first lst
    if i == 0:
        continue
    
    # current list
    for j in range(len(lsts[i])):
        # if first element of a list
        if j == 0:
            lsts[i][j] = lsts[i][j] + lsts[i - 1][j]
        # if last element of a list
        elif j == len(lsts[i]) - 1:
            lsts[i][j] = lsts[i][j] + lsts[i - 1][j - 1]
        else:
            left = lsts[i - 1][j - 1]
            right = lsts[i - 1][j]
            # add up the bigger value
            lsts[i][j] = lsts[i][j] + max(left, right)
    
print(max(lsts[-1]))