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

www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

첫째 줄은 왼쪽 부터 오른쪽으로 dp를 셋팅하고

나머지는 좌우와 위 중 가장 큰값으로 dp를 만들면됨

다만 좌 & 위, 우 & 위로 구하고 그 중 큰값으로 dp를 셋팅하는 방식으로 해야합니다.

이유는 좌를 계산할때 우가 안되있기 때문에

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

// 로봇 조종하기 문제 - 2169번
public class Main {

    static int N, M;
    static int[][] map, dp, temp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

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

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

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

            // 왼쪽 & 위쪽
            temp[0][0] = dp[i-1][0] + map[i][0];
            for(int j = 1; j < M; j++) {
                temp[0][j] = Math.max(temp[0][j-1], dp[i-1][j]) + map[i][j];
            }

            // 오른쪽 & 위쪽
            temp[1][M-1] = dp[i-1][M-1] + map[i][M-1];
            for(int j = M - 2; j >= 0; j--) {
                temp[1][j] = Math.max(temp[1][j+1], dp[i-1][j]) + map[i][j];
            }

            // 그중 최대값
            for(int j = 0; j < M; j++) {
                dp[i][j] = Math.max(temp[0][j], temp[1][j]);
            }
        }
        System.out.println(dp[N-1][M-1]);
    }
}