BOJ_2169_로봇 조종하기 (Java)

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

문제 링크

성능 요약

메모리: 89348 KB, 시간: 532 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 3월 19일 19:19:15

문제 설명

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

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

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

입력

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

출력

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

문제 풀이

dfs로 접근하면 시간초과가 발생한다. 이에 dp를 사용했다. 각 층마다 진행하면 위에서 내려오는것, 왼쪽으로 이동하는것, 오른쪽으로 이동하는것으로 생각할 수 있다.

왼쪽과 오른쪽을 나누어 계산해주면 중복이 없다.

코드

package BOJ_2169_로봇조종하기;

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M, dr[] = {0, 0, 1}, dc[] = {-1, 1, 0};
    static int[][] board, dp;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2169_로봇조종하기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int[][] dp = new int[N][M];
        dp[0][0] = board[0][0];
        for(int j=1; j < M; j++){
            dp[0][j] = dp[0][j-1] + board[0][j];
        }

        for(int i=1; i<N; i++){
            int[] LtoR = new int[M];
            int[] RtoL = new int[M];

            LtoR[0] = dp[i-1][0] + board[i][0];
            for(int j=1; j<M; j++){
                LtoR[j] = Math.max(dp[i-1][j], LtoR[j-1]) + board[i][j];
            }

            RtoL[M-1] = dp[i-1][M-1] + board[i][M-1];
            for(int j=M-2; j>=0; j--){
                RtoL[j] = Math.max(dp[i-1][j], RtoL[j+1]) + board[i][j];
            }

            for(int j=0; j<M; j++){
                dp[i][j] = Math.max(LtoR[j], RtoL[j]);
            }
        }

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