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

11 Nov 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

(0, 0)에서 (N-1, M-1)까지 각 칸의 값을 더하면서 가는데 최댓값을 구해야한다.

이동은 아래, 왼쪽, 오른쪽으로 이동할 수 있다.

첫번째 줄에서는 오른쪽으로 이동할 수 밖에 없다. 첫번째 줄의 dp를 먼저 채우고 아랫줄로 내려간다.

두번째 줄부터는 왼쪽, 오른쪽 모두 이동할 수 있다.

오른쪽으로 가는 경우, 왼쪽으로 가는 경우를 나눠 tmp라는 배열에 저장한다.

이때 위에서 내려오는 값과 바로 옆 칸에서 오는 값을 비교하여 저장한다.

오른쪽, 왼쪽 경우를 비교하여 dp배열에 채운다.

dp[N-1][M-1]을 출력하면 끝.

---

메모리: 79660KB

시간: 608ms

언어: Java 11

코드

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

public class Main {
    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());

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

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

        int[][] tmp = new int[2][M];
        for (int i = 1; i < N; i++) {
            tmp[0][0] = dp[i - 1][0] + arr[i][0];
            for (int j = 1; j < M; j++) {
                tmp[0][j] = Math.max(dp[i - 1][j], tmp[0][j - 1]) + arr[i][j];
            }

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

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

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

}