백준 2169 (로봇 조종하기) - java

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

2169번: 로봇 조종하기

 

문제

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.

각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

 

유형 : DP

 

접근 방식

• 해당 문제를 메모제이션으로 풀려고 여러 번 시도를 했지만 결과는 항상 "틀렸습니다"였다.
  • 여담으로 해당 문제를 메모제이션으로 풀 수 있다는 것을 깨달았다. 하지만 이번 포스팅에서는 정석 풀이를 말하겠다.
• 우선 왼쪽 , 오른쪽 , 아래쪽 3방향으로만 이동 가능하다. 그리고 배열의 값에는 음수도 있다. 
  • 위 조건을 보고 점화식을 세운다면 많이들 이렇게 세울 것이다.
  • dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1] , dp[i][j+1])
• 결과부터 말하자면 위 점화식이 틀린 것은 아니다. 하지만 한번에 저 3값을 비교하는 것은 심각한 오류가 있다.
• (i,j) 좌표의 값을 구하기 위해서는 (i,j+1)의 값이 필요하다. 하지만 동시에 (i,j+1)의 값을 구하기 위해서는 (i,j)의 값이 필요하다.
• 왼쪽과 오른쪽의 값이 동시에 존재하기 때문에 위 점화식으로는 문제를 풀 수 없다.

해결 방법

• 왼쪽과 오른쪽을 따로 구한 다음 마지막에 합치는 것이다. 개인적으로 이 방법에 대해 너무 잘 설명해준 블로그가 있다. 나 또한 이 블로그를 참고 했다. 링크로 남겨두겠다.

https://heedipro.tistory.com/263

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static int[][] board;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][m+1];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(bf.readLine()," ");

            for(int j=1;j<=m;j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] dp = new int[n+1][m+1];

        for(int i=1;i<=m;i++){
            dp[1][i] = dp[1][i-1] + board[1][i];
        }

        for(int i= 2; i <= n ; i++){
            int left[] = new int[m+1];
            int right[] = new int[m+1];

            left[1] = dp[i-1][1] + board[i][1];

            for(int j=2;j<=m;j++){
                left[j] = Math.max(left[j-1],dp[i-1][j]) + board[i][j];
            }

            right[m] = dp[i-1][m] + board[i][m];

            for(int j=m-1;j>=1;j--){
                right[j] = Math.max(right[j+1],dp[i-1][j]) + board[i][j];
            }

            for(int j=1;j<=m;j++){
                dp[i][j] = Math.max(left[j],right[j]);
            }
        }

        System.out.println(dp[n][m]);

        bf.close();
    }
}