https://www.acmicpc.net/problem/1932
Solved
# O(N^2)
import sys
input = sys.stdin.readline
N = int(input())
arr = [list(map(int, input().rstrip().split())) for _ in range(N)]
dp = [[0]*N for _ in range(N)] # 층 별 최대 값
dp[0][0] = arr[0][0]
for i in range(1, N):
for j in range(i+1):
# 대각선 왼쪽에서 내려온 경우
if j > 0:
left = dp[i-1][j-1] + arr[i][j]
else:
left = 0
# 대각선 오른쪽에서 내려온 경우
if j < i:
right = dp[i-1][j] + arr[i][j]
else:
right = 0
dp[i][j] = max(left, right)
print(dp)
print(max(dp[N-1]))
처음엔 그리디라고 생각했지만, 이전 단계까지의 합을 구하는 문제이기에 DP로 풀이방법을 돌렸다.
대각선 왼쪽과 오른쪽에서 내려오는 값중 더 큰 값을 골라 누적합을 구하면 되는 문제!
DP는 코드 구현보다 점화식을 찾는 데에 정말 압도적으로 시간이 많이 든다.
관계 잘 파악하기!