[백준 2169] 로봇 조종하기 - JAVA

BOJ Link

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

 

 

 

풀이 과정

돌아올 때 최적인 경우가 존재하므로 모든 경우를 고려해야 한다. 이는 최대 1000*1000 배열이므로 최적화가 필요하다.

문제에서, 로봇은 위로 이동할 수 없다. 따라서 dp[i][j]가 최적이려면, 왼/오른/위쪽에서 들어오는 경우를 고려해야 한다.

경로에 상관없이 해당 행열에 도달할 때 최대값만을 기록하며, 재방문이 불가능하기에 왼/오/왼같은 탐색은 불가능하다.

 

 

먼저, 배열의 첫 행은 오른쪽으로 밖에 이동할 수 없다. 이를 초기화한다.

이후엔 왼+위, 오+위의 경로를 고려한 left,right 임시 배열을 선언한 후, 둘중 최대 값으로 dp를 갱신한다.

 

제출 코드

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

class Main {
    public static void main(String[] args) throws IOException {

        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());

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

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

        for (int i = 0; i < N; i++) {

            if (i == 0) {
                for (int j = 0; j < M; j++) {
                    if (j == 0) dp[i][j] = map[i][j];
                    else dp[i][j] = dp[i][j - 1] + map[i][j];
                }
            } else {
                int[] left = new int[M];
                int[] right = new int[M];

                for (int j = 0; j < M; j++) {
                    if (j == 0) left[j] = dp[i - 1][j] + map[i][j];
                    else left[j] = Math.max(dp[i - 1][j], left[j - 1]) + map[i][j];
                }

                for (int j = M - 1; j >= 0; j--) {
                    if (j == M - 1) right[j] = dp[i - 1][j] + map[i][j];
                    else right[j] = Math.max(dp[i - 1][j], right[j + 1] + map[i][j];
                }

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

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