[java] 2169번 로봇 조종하기

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

DP를 사용,
왼쪽 오른쪽 아래쪽 만 가능 = 한 줄씩 처리하자!

3. 코드

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

public class Main {

    static int N, M; 
    static int[][] arr, dp, temp; 
    static int MaxResult = 0;
    static int[] dx = {-1,1,0};
    static int[] dy = {0,0,1};

    public static void main(String[] args) throws IOException {
        // 값 입력받기 -->
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = 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++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //<--
        dp[0][0] = arr[0][0];
        for(int i=1;i<M;i++){
            dp[0][i] = dp[0][i-1]+arr[0][i];
        }

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

            //오른쪽&위쪽
            temp[1][M-1] = dp[i-1][M-1] + arr[i][M-1];
            for(int j=M-2;j>=0;j--){
                temp[1][j] = Math.max(temp[1][j+1],dp[i-1][j])+arr[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]);

    }
}

// 참고: https://wellbell.tistory.com/59

백준예시 1과 표로 이해

예시) 5 5
10 25 7 8 13
68 24 -78 63 32
12 -69 100 -29 -25
-16 -22 -57 -33 99
7 -76 -11 77 15

풀이

1. (0,0) 에서 시작할 때, 오른쪽으로만 갈 수 있으니
   dp[0][i] = (0,0)에서부터 i까지 오른쪽으로 합한 값
   

코드에서 아래 부분에 해당

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

2. dp의 첫번째 줄이 구해졌으니 두번째 줄의 왼쪽에서부터의 최댓값을 구함. == 코드상 //왼쪽&위쪽 부분에 해당

temp[0][0] = dp[i-1][0] + arr[i][0];

해당 코드로, temp[0][0] 의 값을 구함 => (0,0)에서 아래로 움직였을 경우

왼쪽&위쪽, i=1 일 때, j=1 인 경우 즉, (1,1)의 왼쪽에서부터의 최댓값을 구함.
(0,0)->(1,0)->(1,1) 이냐, (0,0)->(0,1)->(1,1)이냐를 계산하는 과정
== 10->68->24 이냐, 10->25->24 이냐

j=2 일 때

j=3 일 때 최댓값

j=4 일 때

이렇게 두번째줄 왼쪽 계산 끝.
오른쪽줄 계산

158 = 10+25+7+8+13+32+63 임을 알 수 있음.

이렇게 계산하면 temp[1] 이, 오른쪽에서부터 계산했을 때의 최댓값이 완성됨.

두번째줄의 계산이 끝났으므로,
왼쪽부터 계산=temp[0] , 오른쪽부터 계산=temp[1]을 비교하여 최댓값을 dp[1] 에 넣어줌.

dp[1][0]을 예로 들어 설명하자면,
노란색 영역
(0,0)->(0,1)->(0,2)->(0,3)->(0,4)->(1,4)->(1,3)->(1,2)->(1,1)->(1,0) 의 합임.

이렇게 왼쪽부터~, 오른쪽부터~ 계산하여 최댓값을 구한다음, 줄마다 적용시켜 dp 완성!
완성된 DP

회고

첨에 풀이봤을 때는 뭐지... 했는데, 이렇게 직접 표로 그리고 나니 이해가 된다.
이런 방식을 생각해내는 것도 정말 천재인 것 같다.
DP문제 많이 풀어야겠당