[DP 알고리즘] 정수 삼각형 S1

기출 : BOJ #1932

 

n번째 줄 m번째 위치를 고르는 경우 이는 n-1번째 줄의 m-1번째, m번째 위치로부터 내려온다 (확장성)

이를 고려하면 점화식은 다음과 같다

 

D[n][m] = n번째 줄 m번째 숫자를 고르는 경우 최댓값

D[n][m] = max(D[n-1][m-1], D[n-1][m]) + tri[n][m]

 

 

# d[n][m] = max(d[n-1][m-1], d[n-1][m]) + tri[n][m]

n = int(input())
tri = list()
d = [[0 for j in range(i+1)] for i in range(n)]
for _ in range(n):
    tri.append(list(map(int,input().split())))

d[0][0] = tri[0][0]

for i in range(1,n):
    for j in range(i+1):
        if j==0:
            d[i][j] = d[i-1][j] + tri[i][j]
        elif j==i:
            d[i][j] = d[i-1][j-1] + tri[i][j]
        else:
            d[i][j] = max(d[i-1][j-1], d[i-1][j]) + tri[i][j]

print(max(d[n-1]))