[백준 2169] 로봇 조정하기 / 자바 / dp

#문제         

레벨: G5
알고리즘: dp 
풀이시간: 20분 
힌트 참조 유무: 유

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

 

---

#문제 풀이        

 

• Top-down DP (DFS + DP):
  • 재귀를 사용
  • 메모이제이션(기존에 계산한 값을 저장)
  • 큰 문제를 작은 문제로 나누어 해결
  • 주로 @(재귀 + 메모이제이션) 방식으로 구현
• Bottom-up DP:
  • 반복문을 사용
  • 작은 문제부터 차례대로 해결
  • 반복문으로 점화식 구현
  • 테이블을 채워나가는 방식

// top-down
int fibonacci(int n) {
    if (dp[n] != -1) return dp[n];
    if (n <= 1) return n;
    dp[n] = fibonacci(n-1) + fibonacci(n-2);
    return dp[n];
}


// bottom-up
int fibonacci(int n) {
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

 

---

#풀이 코드      

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