참고 |https://soohyun6879.tistory.com/157

동적계획법 프로그래밍

참고글 동적 계획법 개념 정리 및 예제 정리

문제

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

코드

T = int(input())
dp = []
for i in range(T):
    dp.append(list(map(int, input().split())))



for i  in range(1,T):
    for j in range(0,i+1):
        # 가장 왼쪽에 있는 경우
        if j == 0:
            dp[i][0] += dp[i-1][0] # 덧셈 전 부분  

        # 가장 오른쪽에 있을 경우
        elif i == j:
            dp[i][j] += dp[i-1][j-1]
        
        else: # 가운데 있을 경우[가지치기 경우의 수 고려 --> 가지치기 자체를 max로 선택]

            dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])

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


# 시간복잡도를 생각하자 -> O(n^2)

해설은 이 부분을 참고하면 된다. 동적계획법이라는 문제를 처음 접하게 되었다. 앞으로 30문제를 풀어볼 예정이다. 쉽진 않겠지만 도전하자!