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

문제 링크

성능 요약

메모리: 84312 KB, 시간: 2120 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 7일 17:18:00

문제 설명

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

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

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

입력

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

출력

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

---

풀이

• 첫 번째 Row에서는 (1,1)에서 시작하므로 아래 혹은 오른쪽으로만 이동 가능하다.
• 두 번째 Row부터는 바로 위 Row에서 내려온 후, 왼쪽 혹은 오른쪽으로 이동 가능하다.
  따라서 모든 경우를 따져 최대 가치 갱신한다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int[][] a;
    static int[][] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        a = new int[N][M];
        dp = new int[N][M];

        for (int i = 0; i < N; i++)
            Arrays.fill(dp[i], Integer.MIN_VALUE);

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        explore();

        System.out.println(dp[N - 1][M - 1]);
    }

    static void explore() {
        for (int row = 0; row < N; row++) {
        	// 첫 번째 Row는 (1,1) 에서 시작해서 오른쪽으로만 이동 가능
            if (row == 0) {
                dp[0][0] = a[0][0];

                for (int i = 1; i < M; i++) {
                    dp[row][i] = dp[row][i - 1] + a[row][i];
                }
                continue;
            }

			// 두 번째 Row부터는 위에서 내려와서 좌, 우로 이동 가능
            int[] tmp = new int[M];
            for (int col = 0; col < M; col++) {
                tmp[col] = dp[row - 1][col] + a[row][col]; // 임시 가치
                dp[row][col] = Math.max(dp[row][col], tmp[col]); // 높은 가치로 갱신

				// 왼쪽으로 이동하며 가치 갱신
                for (int i = col - 1; i >= 0; i--) {
                    tmp[i] = tmp[i + 1] + a[row][i];
                    dp[row][i] = Math.max(dp[row][i], tmp[i]);
                }

				// 오른쪽으로 이동하며 가치 갱신
                for (int i = col + 1; i < M; i++) {
                    tmp[i] = tmp[i - 1] + a[row][i];
                    dp[row][i] = Math.max(dp[row][i], tmp[i]);
                }
            }

        }
    }

}