[Python/BOJ] 2169. 로봇 조종하기

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

2169번: 로봇 조종하기

문제

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.

각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

출력

첫째 줄에 최대 가치의 합을 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

def solution(n, m, array):
    # 1. DP 생성
    dp = [[[0, 0] for _ in range(m)] for _ in range(n)]
    # 2. 초기값 설정
    dp[0][0] = [array[0][0]] * 2
    for y in range(1, m) : dp[0][y] = [dp[0][y-1][0] + array[0][y]] * 2
    # 3.
    for x in range(1, n) :
        # 3-1.
        for y in range(m) :
            # 3-1-1. 점화식에 따라 이전 행 정보 가져오기
            dp[x][y] = [max(dp[x-1][y]) + array[x][y]] * 2
        # 3-2.
        for y in range(m) :
            L2R, R2L = y, m - 1 - y
            # 3-2-1 왼쪽에서 오른쪽으로 이동이 가능한 경우 점화식에 따라 처리
            if L2R + 1 < m : dp[x][L2R+1][0] = max(dp[x][L2R+1][0], dp[x][L2R][0] + array[x][L2R+1])
            # 3-2-2. 오른쪽에서 왼쪽으로 이동이 가능한 경우
            if R2L - 1 >= 0 : dp[x][R2L-1][1] = max(dp[x][R2L-1][1], dp[x][R2L][1] + array[x][R2L-1])
    # 4. 결과 출력
    print(max(dp[-1][-1]))

if __name__ == "__main__":
    n, m = map(int, input().split())
    array = [list(map(int, input().split())) for _ in range(n)]
    solution(n, m, array)