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

풀기 전 생각

'''
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,)
'''

순방향

첫번째 풀이

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]))

역방향

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])