백준 2169. 로봇 조종하기

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

import sys

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

# DP 테이블의 첫 번째 행(무조건 왼쪽->오른쪽)
for j in range(1, m):
    dp[0][j] += dp[0][j-1]

# 나머지 행 처리
for i in range(1, n):
    left_to_right = dp[i][:] # 왼쪽 -> 오른쪽
    right_to_left = dp[i][:] # 오른쪽 -> 왼쪽

    # 왼쪽-> 오른쪽
    for j in range(m):
        # 첫번째 열일 경우, 위에서 오는 경우 밖에 없으므로
        if (j == 0):
            left_to_right[j] += dp[i-1][j]
        # 나머지 열에 대해, 위에서 내려오는 경우와 왼쪽에서 오는 경우를 비교
        else:
            left_to_right[j] += max(dp[i-1][j], left_to_right[j-1])

    # 오른쪽-> 왼쪽
    for j in range(m-1, -1, -1):
        # 마지막 열일 경우, 위에서 오는 경우 밖에 없으므로
        if (j == m-1):
            right_to_left[j] += dp[i-1][j]
        # 나머지 열에 대해, 위에서 내려오는 경우와 오른쪽에서 오는 경우를 비교
        else:
            right_to_left[j] += max(dp[i-1][j], right_to_left[j+1])

    # 두 가지 임시 배열을 비교해, 각 좌표값들을 최대값으로 업데이트
    for j in range(m):
        dp[i][j] = max(left_to_right[j], right_to_left[j])

print(dp[n-1][m-1])