계산 로봇

• 간단한 2차원 DP 문제.
• 로봇의 입력값이 될수 있는 범위가 그 로봇을 꼭짓점으로 하는 삼각형 전체 영역으로 되어있긴 하지만, 그중에서 최댓값을 찾기 위해서는 바로 왼쪽열의 3칸만 비교해보면 된다. 따라서 (i,j)로봇의 저장값을 dp[i][j]라고 하면 dp[i][j] = max(dp[i-1][j-1] + D[i-1][j-1], dp[i][j-1] + D[i][j-1], dp[i+1][j-1] + D[i+1][j-1]) 의 간단한 점화식으로 표현될수 있다. M*N 크기의 DP 테이블을 채우는 것은 O(MN)에 채울수 있다.
• 식 자체는 간단하고 전형적인 2차원 DP이긴 한데.. 파이썬으로는 시간 제한이 빡빡하다. 그냥 일반적으로 구현하면 파이썬으로는 2초 안에 안돌아가고, PyPy로는 400ms 정도가 걸린다.
  • M*N 이 최대 4백만밖에 안되는데도 2초 안에 돌리기 위해서 최적화가 필요하다는 것은 좀 심하긴 하다…
• 파이썬으로 돌리기 위해서는 코드레벨 최적화가 필요하다.. DP 에 로봇의 저장값 대신에 로봇의 출력값을 저장하는 식으로 해서 연산량을 살짝 줄이고 (대신 최종 답을 계산할때 출력값을 저장값으로 변환해야 해서 코드가 좀더 지저분해진다), 리스트에 인덱스로 접근하는 것을 최대한 피하는 방식으로 줄인결과 1900ms 정도에 가까스로 통과했다.

"""Solution code for "BOJ 22342. 계산 로봇".

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

import sys


def main():
    # pylint: disable=unused-variable
    M, N = [int(x) for x in sys.stdin.readline().split()]
    D = [[int(x) for x in sys.stdin.readline().rstrip()] for _ in range(M)]

    dp_cur = [0] * M
    for j in range(N - 1):
        dp_prev, dp_cur = dp_cur, [0] * M
        for i in range(M):
            dp_cur[i] = max(
                dp_prev[x] + D[x][j] for x in (i - 1, i, i + 1) if 0 <= x < M)
    print(max(dp_cur))


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 22342. 계산 로봇".

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

import sys


def main():
    # pylint: disable=unused-variable
    M, N = [int(x) for x in sys.stdin.readline().split()]
    D = [[int(x) for x in sys.stdin.readline().rstrip()] for _ in range(M)]

    if M == 1:
        print(sum(D[0][:-1]))
        return

    dp_cur = [0] * M
    for d_col in zip(*D):
        dp_prev, dp_cur = dp_cur, []
        dp_cur.append(max(dp_prev[0], dp_prev[1]) + d_col[0])
        dp_cur.extend(
            max(x, y, z) + d
            for x, y, z, d in zip(dp_prev, dp_prev[1:], dp_prev[2:], d_col[1:]))
        dp_cur.append(max(dp_prev[-1], dp_prev[-2]) + d_col[-1])

    print(max(dp_cur[i] - D[i][-1] for i in range(M)))


if __name__ == '__main__':
    main()