[백준][Python] 1932번 정수 삼각형 - DP

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

1932번: 정수 삼각형

 

 

Python

n = int(input())
dp = [0]
dp.append(int(input()))  # nn==1


cnt = 0

for n in range(1, n):
    k = list(map(int, input().split()))

    for r in range(1, len(k)+1):
        if r == 1:
            dp.append(k[r-1] + dp[cnt+r])  # (n-1, r))
            #print(dp, dp[cnt+r])
        elif r == len(k):
            dp.append(k[r-1] + dp[cnt+r-1])  # (n-1, r-1))
            #print(dp, dp[cnt+r-1])
        else:
            dp.append(k[r-1] + max(dp[cnt+r], dp[cnt+r-1]))
    cnt += len(k)-1  # 두 번째 전의 끝을 봐야 직전의 항을 건드릴 수 있다


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

 

 

풀이

상단의 두 항 중 큰 값과 현재 값을 더하는 식으로 진행

https://en.wikipedia.org/wiki/Pascal%27s_triangle