백준 정수 삼각형 코드 및 해설 (파이썬)

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

1932번: 정수 삼각형

 

모든 정수를 거쳐가며 다음을 처리합니다.
첫 행은 아무 계산도 하지 않습니다
2번째 행부터 중간에 위치한 정수들은 직전 행의 오른쪽, 왼쪽 대각선의 수 중 큰 것을 더합니다. 첫 번째에 위치한 정수들은 직전 행의 첫 번째 수를 더합니다. 마지막에 위치한 정수들은 직전 행의 마지막 수를 더합니다.
계산이 끝난 후 마지막 행의 최댓값을 반환합니다.

• 시간 복잡도: O(N)

 

import sys

# 입력 처리하기
nums = []
# 삼각형의 크기
N = int(sys.stdin.readline())
for i in range(N):
    nums.append(list(map(int, sys.stdin.readline().split())))

for i, num in enumerate(nums):
    # 첫 행
    if i == 0 :
        continue
    for j in range(i+1):
        # i행의 첫 번째 숫자: 직전 행의 첫 번째 숫자에서만 접근 가능
        if j == 0:
            nums[i][j] += nums[i-1][j]
        # i행의 마지막 숫자: 직전 행의 마지막 숫자에서만 접근 가능
        elif j == i:
            nums[i][j] += nums[i - 1][j-1]
        # 직전 행의 왼쪽, 오른쪽 대각선에서 모두 접근 가능
        else:
            nums[i][j] += max(nums[i-1][j-1], nums[i-1][j])

# 마지막 행의 최댓값 
print(max(nums[-1]))