[백준 1932 정수 삼각형 문제] PYTHON

 

이번에도 DP 문제다.

문제 접근 방식은 전과 같았다.

 

7

3 8 이면

 

7

10 15 로 값을 내리며 최댓값을 배열에 저장한다.

 

이차원 배열로 접근 해야하기 때문에 [i][i]는 [i-1][i-1]과 [i-1][i]의 max 값을 [i][i]에 더하면 됐다.

참고로 맨끝에 있는 배열의 경우 index error가 날 수 있으므로 예외처리해야한다.

 

N = int(input())
cost= []
dp = [0 for i in range(501)]
for _ in range(N):
    cost.append(list(map(int, input().split())))

for i in range(1,N):
    for j in range(1,i):
        cost[i][j]=max(cost[i-1][j-1],cost[i-1][j])+cost[i][j]
    cost[i][0]=cost[i-1][0]+cost[i][0]
    cost[i][i]=cost[i-1][i-1]+cost[i][i]
print(max(cost[N-1]))