로봇 조종하기

• 만약 아래쪽과 오른쪽으로만 이동이 가능하다면, 굉장히 흔한 기초 DP문제이지만, 왼쪽으로도 이동이 가능하기때문에 좀더 생각해야 하는 문제가 되었다.
• 같은칸을 중복방문할수 없다는 이야기는, 같은 행에서는 왼쪽이나 오른쪽 한쪽 방향으로만 이동해야 한다는 말이다.
• 그렇다면, (r,c)위치까지 왔을때의 최대 가치를 dp[r][c]라고 했을때, 이것을 왼쪽에서 이동해 왔을 경우와 오른쪽에서 이동해 왔을 경우의 각각의 최대값중에서 더 큰 값을 고르는 방식으로 구할수 있다. 왼쪽에서 오른쪽 방향으로 왔을때의 최대가치를 dp_r[r][c], 왼쪽 방향으로 왔을때의 최대가치를 dp_l[r][c]라고 하면 점화식을 다음처럼 쓸수 있다.
  • dp_r[r][c] = max(dp_r[r][c - 1], dp[r - 1][c]) + val[r][c]
  • dp_l[r][c] = max(dp_l[r][c + 1], dp[r - 1][c]) + val[r][c]
  • dp[r][c] = max(dp_r[r][c], dp_l[r][c]
• 이 dp 테이블의 각 셀은 O(1)에 구할수 있으므로, dp 테이블 전체를 채우는 데에는 O(n*m)이 걸린다.

"""Solution code for "BOJ 2169. 로봇 조종하기".

- Problem link: https://www.acmicpc.net/problem/2169
- Solution link: http://www.teferi.net/ps/problems/boj/2169

Tags: [DP]
"""

import sys

INF = float('inf')


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    grid = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    dp_cur = [-INF] * M
    dp_cur[0] = 0
    for row in grid:
        dp_prev = dp_cur
        dp_l, dp_r = [None] * M, [None] * M
        prev = -INF
        for i, row_i, dp_prev_i in zip(range(M), row, dp_prev):
            dp_r[i] = prev = max(prev, dp_prev_i) + row_i
        prev = -INF
        for i, row_i, dp_prev_i in zip(reversed(range(M)), reversed(row),
                                       reversed(dp_prev)):
            dp_l[i] = prev = max(prev, dp_prev_i) + row_i
        dp_cur = [max(vals) for vals in zip(dp_r, dp_l)]

    print(dp_cur[-1])


if __name__ == '__main__':
    main()