https://www.acmicpc.net/problem/2169
if __name__ == "__main__":
n,m = map(int,input().split())
dp = [list(map(int,input().split())) for _ in range(n)]
for i in range(1,m):
dp[0][i] += dp[0][i-1]
for i in range(1,n):
left = dp[i][:]
right = dp[i][:]
for j in range(m):
if j == 0:
left[j] += dp[i-1][j]
else:
left[j] += max(dp[i-1][j],left[j-1])
for j in range(m-1,-1,-1):
if j == m-1:
right[j] += dp[i-1][j]
else:
right[j] += max(dp[i-1][j],right[j+1])
for j in range(m):
dp[i][j] = max(left[j],right[j])
print(dp[n-1][m-1])
탐색하는 방법은 위에서 오는 경우, 왼쪽에서 오는 경우, 오른쪽에서 오는 경우이다. 이때 어디서 오는 값이 최대값인지 탐색해야한다.
3.한 행씩 왼>오/오>왼을 비교해서 임시배열에 넣어주고 각 임시배열을 순차적으로 비교해서 최대갮을 DP[i][j]에 넣어준다.
처음에 방문했던 곳은 다시 재방문하지 않는다와 2차원 배열 탐색만 보고 BFS + Visited 체크해서 푸는 완전탐색으로 접근하고 문제를 풀었다 당연히 시간초과 ;;;
이럴 때 혹시 ~ 하면서 pypy3로 돌려보면 메모리 초과가 난다 ; ㅋ
재방문 하지 않는다의 뜻은 왼쪽에서 왔을 때 다시 왼쪽을 탐색하지 말라는 뜻인데 그걸 몰랐다.
어디까지 탐색하고 그 다음을 탐색할 때 값이 정해지고 특정 부분부터 새로운 탐색이 시작되면 특정 부분 이전은 고정이니까 메모이제이션을 통해서 저장해야겠다. 라는 생각을 해야한다.
또 완전탐색인가? 시간초과 나겠다 그러면 DP이다. DP면 규칙이 있을 것이다. 라는 생각을 가지고 문제에 접근하자