[Gold II] 로봇 조종하기 - 2169

문제 링크

성능 요약

메모리: 83236 KB, 시간: 588 ms

분류

다이나믹 프로그래밍

문제 설명

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

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

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

입력

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

출력

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

풀이과정 (다이나믹 프로그래밍)

우선 왼쪽 , 오른쪽 , 아래쪽 3방향으로만 이동 가능하다.

위의 경우들을 각 줄마다 고려하여 해당 값 중 제일 큰 값을 골라 더해주면 된다.

예제 입력

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

dp 배열 초기화 (첫 번째 행)

첫 번째 행은 왼쪽에서 오는 값만 고려하여 계산됩니다.

10   35   42   50   63

dp[0][0] = 10
dp[0][1] = 10 + 25  = 35
dp[0][2] = 35 + 7   = 42
dp[0][3] = 42 + 8   = 50
dp[0][4] = 50 + 13  = 63

두 번째 행 (i = 1)

temp 배열은 두 방향에서 오는 값을 한 번에 계산하고 이를 dp 배열에 반영하기 위해 사용됩니다.

(1) 왼쪽 → 오른쪽 (temp[0])

temp[0][j] = Math.max(temp[0][j - 1], dp[i - 1][j]) + map[i][j];

• 위쪽에서 오는 값: dp[i - 1][j] (현재 칸의 바로 위의 값)

• 왼쪽에서 오는 값: temp[0][j - 1] (현재 칸의 왼쪽에 있는 값)

78   102   24   113   145

temp[0][0] = dp[0][0] + map[1][0] = 10 + 68 = 78
temp[0][1] = max(temp[0][0], dp[0][1]) + map[1][1] = max(78, 35) + 24 = 102
temp[0][2] = max(temp[0][1], dp[0][2]) + map[1][2] = max(102, 42) - 78 = 24
temp[0][3] = max(temp[0][2], dp[0][3]) + map[1][3] = max(24, 50) + 63 = 113
temp[0][4] = max(temp[0][3], dp[0][4]) + map[1][4] = max(113, 63) + 32 = 145

(2) 오른쪽 → 왼쪽 (temp[1])

temp[1][j] = Math.max(temp[1][j + 1], dp[i - 1][j]) + map[i][j];

• 위쪽에서 오는 값: dp[i - 1][j] (현재 칸의 바로 위의 값)

• 오른쪽에서 오는 값: temp[1][j + 1] (현재 칸의 왼쪽에 있는 값)

172   104   80   158   95

temp[1][4] = dp[0][4] + map[1][4] = 63 + 32 = 95
temp[1][3] = max(temp[1][4], dp[0][3]) + map[1][3] = max(95, 50) + 63 = 158
temp[1][2] = max(temp[1][3], dp[0][2]) + map[1][2] = max(158, 42) - 78 = 80
temp[1][1] = max(temp[1][2], dp[0][1]) + map[1][1] = max(80, 35) + 24 = 104
temp[1][0] = max(temp[1][1], dp[0][0]) + map[1][0] = max(104, 10) + 68 = 172

(3) dp 값 업데이트 (두 값 중 최대 선택)

dp[i][j] = Math.max(temp[0][j], temp[1][j]);

172   104   80   158   145

최종 출력값

dp[4][4] = 319

import java.util.*;
import java.io.*;

class Main {
    static int n, m;
    static int[][] map, dp, temp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        dp = new int[n][m];
        temp = new int[2][m];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[0][0] = map[0][0]; // 시작점
        for(int i = 1; i < m; i++) {
            d[0][i] = dp[0][i - 1] + map[0][i]; // 첫 번째 행(왼쪽에서)
        }

        for(int i = 1; i < n; i++) {
            // 왼쪽&위쪽에서
            temp[0][0] = dp[i - 1][0] + map[i][0];
            for(int j = 1; j < m; j++) {
                teomp[0][j] = Math.max(temp[0][j - 1], dp[i - 1][j]) + map[i][j];
            }

            // 오른쪽&위쪽에서
            temp[1][m - 1] = dp[i - 1][m - 1] + map[i][m - 1]; //마지막점(위쪽에서)
            for(int j = m - 2; j >= 0; j--) {
                temp[1][j] = Math.max(temp[1][j + 1], dp[i - 1][j]) + map[i][j];
            }

            // 그중 최대값
            for(int j = 0; j < m; j++) {
                dp[i][j] = Math.max(temp[0][j], temp[1][j]);
            }
        }
        System.out.println(dp[n - 1][m - 1]);
    }
}