백준 / 실버 1 / 1932 정수 삼각형 / Python [2차원 DP, 부분합]

풀기 전 생각

'''
2초 2,000,000,000
500*500*500 = 125,000,000
최대 O(N3)

2^500 절대 불가

10 = max(0-1, 00)
11 = max(00, 01)
20 = max(10, 11)
21 = max(10,)
'''

1. 순방향 (발산형)

첫번째 풀이

import sys
input = sys.stdin.readline

n = int(input())
num = [list(map(int, input().split())) for _ in range(n)]
for i in range(1, n):
    for j in range(i+1):
        l = max(j-1, 0)
        r = min(j, i-1)
        num[i][j] = max(num[i-1][l], num[i-1][r]) + num[i][j]
print(max(num[n-1]))

2. 역방향 (수렴형)

두번째 풀이

import sys
input = sys.stdin.readline

n = int(input())
num = [list(map(int, input().split())) for _ in range(n)]
for i in range(n-2, -1, -1):
    for j in range(i+1):
        num[i][j] = max(num[i+1][j], num[i+1][j+1]) + num[i][j]
print(num[0][0])

발산형과 달리
범위 컷오프하는 과정,
max()로 마지막 O(N) 순회하는 과정이 필요 없어졌다.