백준 1932(정수 삼각형) - Python(파이썬) -DP

1932번: 정수 삼각형

예제 풀이

	j=0	j=1	j=2	j=3	j=4
dp[0]	dp[0][0] = 7
dp[1]	dp[0][0] +dp[1][0] = 7 + 3 = 10	dp[0][0] +dp[1][1]  = 7 + 8 = 15
dp[2]	dp[1][0] +dp[2][0]  = 10 + 8 = 18	max( dp[1][0]+dp[2][1], dp[1][1]+dp[2][1] ) = max(11,16) =16	dp[1][1] +dp[2][2]  = 15 + 0 = 15
dp[3]	dp[2][0] +dp[3][0]  = 18 + 2 = 20	max( dp[2][0]+dp[3][1], dp[2][1]+dp[3][1] ) = max(25,23) =25	max( dp[2][1]+dp[3][2], dp[2][2]+dp[3][2] ) = max(20,19) =20	dp[2][2] +dp[3][3]  = 15 + 4 = 19
dp[4]	dp[3][0] +dp[4][0]  = 20 + 4 = 24	max( dp[3][0]+dp[4][1], dp[3][1]+dp[4][1] ) = max(25,30) =30	max( dp[3][1]+dp[4][2], dp[3][2]+dp[4][2] ) = max(27,22) =27	max( dp[3][2]+dp[4][3], dp[3][3]+dp[4][3] ) = max(26,25) =26	dp[3][3] +dp[4][4]  = 19+5 = 24

dp[i]의 양 끝을 제외하고는 dp[i-1][j-1] 와 dp[i-1][j] 를 비교하여 최댓값을 더한다.

dp[i]의 j==0인 경우 -> dp[i][j] += dp[i-1] 

dp[i]의 j==맨 끝의 경우 -> dp[i][j] += dp[i-1][j-1]

 

문제 풀이

💻Python(파이썬)

import sys
n = int(sys.stdin.readline())
dp =[]
for i in range(n):
    dp.append(list(map(int,sys.stdin.readline().split())))

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

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