[python 백준] 1932번 : 정수 삼각형

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

해당 문제를 bfs로 풀어보니 계속 시간초과가 발생했다.

동적프로그래밍으로 풀어야하는 문제이다. 하지만 동적프로그래밍은 항상 어렵다.

import sys
input = sys.stdin.readline


n = int(input())
triangle = list()

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

 트리구조의 리스트 이기  때문에 밑에서 부터 큰값을 선택해가며 위로 누적하며 올라가면 최대값이 구해지는 원리이다. 왜.. 나는 이것을 생각해내지 못했을까.. 슬프다..