[백준] [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], ", index =", 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], ", index =", cnt+r-1)
        else: # 왼,오 중에서 큰 값으로 덧셈하여 진행
            dp.append(k[r-1] + max(dp[cnt+r], dp[cnt+r-1]))
            #print(dp, max(dp[cnt+r], dp[cnt+r-1]))
    
    cnt += len(k)-1  # 두 번째 전의 끝을 봐야 직전의 항을 건드릴 수 있다             
    
    
print(max(dp[-n:]))    # 마지막 줄에서 최대값 찾기

 

 

 

풀이