[다이나믹 프로그래밍] 백준 1932번: 정수 삼각형

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

그리디로 생각하기 쉽지만 dp문제이다.

매번 큰수를 택하는 식으로 접근하면(그리디) 문제가 풀리지 않는다.

n = int(input())
triangle=[]
for i in range(n):
    triangle.append(list(map(int,input().split())))

dp =[triangle[0][0]]
for i in range(1,n): # i means depth
    ndp = []
    for j in range(i+1):
        if j==0 : # left edge
            pre = dp[j]
        elif j==i: # right edge
            pre = dp[j-1]
        else:
            pre = max(dp[j-1], dp[j])
        ndp.append(pre + triangle[i][j])
    dp = ndp
print(max(dp))