[백준 - 2169][Gold2 ][해설 X] - 로봇 조종하기 (JAVA)

문제 링크

---

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

 

문제

---

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

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

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

 

입력

---

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

 

출력

---

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

 

헤결 코드

---

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

public class Main {
    static int [][] map;
    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());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

        for(int i=0;i<map.length;i++){
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        dp[0][0] = map[0][0];
	
    	//첫번째 배열은 무조건 왼쪽으로만 가능
        for(int j=1;j<dp[0].length;j++){
            dp[0][j] = map[0][j] + dp[0][j-1];
        }

        for(int i=1;i<map.length;i++){
        	//왼쪽에서 시작하는 최대값 배열 구하기
       		int[] leftDp = new int[M];
            leftDp[0] = dp[i-1][0] + map[i][0];
		
            for(int j=1;j<map[i].length;j++) {
                leftDp[j] = Math.max(leftDp[j-1],dp[i-1][j]) + map[i][j];
            }

        	//오른쪽에서 시작하는 최대값 배열 구하기
            int[] rightDp = new int[M];
            rightDp[map[i].length-1] = dp[i-1][map[i].length-1] + map[i][map[i].length-1];

            for(int j=map[i].length-2;j>=0;j--) {
                rightDp[j] = Math.max(rightDp[j+1],dp[i-1][j]) + map[i][j];
            }

			//왼쪽,오른쪽의 최대값 배열 구하기
            for(int j=0;j<dp[i].length;j++){
                dp[i][j] = Math.max(leftDp[j],rightDp[j]);
            }
        }

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

 

 

실행 결과

---