자바 - 백준 2169 / 로봇 조종하기

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

골드2

풀이 방법

• 단순 dfs로 하면 시간 초과 발생합니다. (시간 복잡도: O(3^(N * M))
  • N, M(1≤N, M≤1,000)
• 현재 문제는 “각 칸까지 올 수 있는 최적 해를 모아 두고, 그 위에서 다음 칸의 최적 해를 구한다”가 목표
  • → DP 생각하기
• 이동 경로 가능 경로: 오른쪽, 왼쪽, 아래
• 따라서 위에서 부터 오른쪽에서 왼쪽으로 갈 때 max값과 왼쪽에서 오른쪽으로 갈 때 max값을 구한 뒤
  • 두 값중 더 큰 값을 아래로 내려주면 된다.
  • 이때 시작은 0,0에서 하기 때문에 이 경우에는 왼쪽에서 오른쪽의 경우만 생각하면 된다.
• dp 시간 복잡도
  • 매 행마다 두 번의 선형 스윕을 수행하므로 O(N×M)

코드

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

/**
* 백준 2169
* 로봇 조종하기
* 골드2
* https://www.acmicpc.net/problem/2169
*/
public class Boj2169 {

    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[][] area = new int[N][M];

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

        int[][] dp = new int[N][M];
        dp[0][0] = area[0][0];
        for(int j = 1; j < M; j++)
            dp[0][j] = dp[0][j - 1] + area[0][j]; // 시작은 오른쪽만

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

            // 왼쪽 -> 오른쪽
            left[0] = dp[i - 1][0] + area[i][0];
            for(int j = 1; j < M; j++)
                left[j] = Math.max(dp[i - 1][j], left[j - 1]) + area[i][j];

            // 오른쪽 -> 왼쪽
            right[M - 1] = dp[i - 1][M - 1] + area[i][M - 1];
            for(int j = M - 2; j >= 0; j--)
                right[j] = Math.max(dp[i - 1][j], right[j + 1]) + area[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]);
    }

}