[Baekjoon] #1932 정수삼각형

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력 및 출력

내가 생각한 logic및 코드

'''logic
    "누적" => 케이스 쪼개서 생각함.
    1. 각 줄의 양 끝에 있는 숫자들은 바로 윗 줄의 숫자를 더해주면 된다.
    2. 사이에 있는 숫자는 왼쪽 대각선과 오른쪽 대각선 중 최댓값에 더해나가면 된다.
    3. 결국은 최댓값 찾고 누적합.
    '''

n = int(input())
num = []

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

# 맨 꼭대기는 for문 돌릴필요 없음.
for i in range(1, n):
    for j in range(len(num[i])):
        # 각 라인의 제일 첫 숫자
        if j == 0:
            num[i][j] = num[i][j] + num[i-1][j]
        # 각 라인의 제일 마지막 숫자
        elif j == len(num[i])-1:
            num[i][j] = num[i][j] + num[i-1][j-1]
        # 위의 경우 제외한 나머지 경우
        else:
            num[i][j] = max(num[i-1][j-1], num[i-1][j]) + num[i][j]

# 맨 마지막 줄(누적합)에서 최댓값 출력
print(max(num[n-1]))