[2169] 로봇 조종하기

문제

백준 문제

 

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

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

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

입력

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

출력

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

예제 입력 1 

5 5
10 25 7 8 13
68 24 -78 63 32
12 -69 100 -29 -25
-16 -22 -57 -33 99
7 -76 -11 77 15

예제 출력 1 

319

---

풀이

import sys
input = sys.stdin.read

def mars_exploration(N, M, grid):
    # DP 테이블 초기화
    dp = [[0] * M for _ in range(N)]

    # 첫 번째 행 초기화 (출발점에서 오른쪽으로만 진행 가능)
    dp[0][0] = grid[0][0]
    for j in range(1, M):
        dp[0][j] = dp[0][j - 1] + grid[0][j]

    # 각 행에 대해 DP 진행
    for i in range(1, N):
        # 위에서 내려오는 값
        upper = dp[i - 1][:]

        # 왼쪽 -> 오른쪽으로 최대값 갱신
        left_to_right = [0] * M
        left_to_right[0] = upper[0] + grid[i][0]
        for j in range(1, M):
            left_to_right[j] = max(left_to_right[j - 1], upper[j]) + grid[i][j]

        # 오른쪽 -> 왼쪽으로 최대값 갱신
        right_to_left = [0] * M
        right_to_left[M - 1] = upper[M - 1] + grid[i][M - 1]
        for j in range(M - 2, -1, -1):
            right_to_left[j] = max(right_to_left[j + 1], upper[j]) + grid[i][j]

        # 현재 행에서 왼쪽, 오른쪽에서 오는 최대값을 DP 테이블에 저장
        for j in range(M):
            dp[i][j] = max(left_to_right[j], right_to_left[j])

    # 최종 목적지의 최대 가치 출력
    return dp[N - 1][M - 1]

# 입력 처리
input_data = input().splitlines()
N, M = map(int, input_data[0].split())
grid = [list(map(int, input_data[i + 1].split())) for i in range(N)]

# 결과 출력
print(mars_exploration(N, M, grid))

 

---