문제

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

나의 코드 (답안 참조)

"""
1. 아이디어
그림 그려서 생각하고 그대로 dp를 2차원 배열로 받아 구현하면 되는 문제이다.
다만 반복문 내에서 원소의 위치에 따라 무엇을 더해줘야 할지 헷갈리는 부분이 있으니 주의하자.

2. 시간복잡도
O(N^2) 이정도?
"""

from sys import stdin
input = stdin.readline

n = int(input())
dp = [ list(map(int, input().split())) for _ in range(n) ]

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]))
    

느낀점

그림 그려서 생각해보면 쉽다.