[백준] 로봇 조종하기(2169): DP - Java

1. 문제

 

 

요약

양옆, 밑으로 가면서 얻을 수 있는 최대 가치의 합 구하기

 

 

2. 접근

몇일 전 코테 봤을 때 문제랑 비슷해서 다시 풀어봤다. 과거에 풀었던건데 코테 때는 생각도 안났다.

 

고민했던 부분

- BFS하면 무조건 시간초과 날 것 같음. 그러면 DP인데 어떻게 구하지?

- DP로 중복 방문을 어떻게 체크하지?

- 다음 칸으로 가는 경우가 3가지인데, 어떤 기준으로 갱신을 해주지?

 

이런 문제 처럼 그래프 문제 같은데, 그렇게 하다간 분명 시간초과가 날것 같을 때. 

문제에 힌트가 있다. 바로 위로는 못 간다는 것이다. 무조건 아래로만 갈 수 있다. 

 

 

3. 알고리즘

위로는 안가니깐 밑으로 내려가기 전에, 해당 층에서 얻을 수 있는 최대 이익을 구한다.

 

방문했던 칸은 다시 안간다고 했다. 그러면 갈 수 있는 방법은, 

1. 위에서 아래로 내려온다.
2. 오른쪽으로 쭉 간다.
3. 왼쪽으로 쭉 간다.

이다.

 

오른쪽 갔다가 왼쪽가는 경우는 절대 없다는 것이다. 그러므로 3가지 경우에 대해서 구현하면 된다.

 

1. 위에서 아래로

// 위에꺼 밑으로 그대로 전달
for(int j=0; j<M; j++){
    dp[i][j] = dp[i-1][j] + map[i][j];
}

(i는 i층을 나타낸다.)

 

우선 밑으로는 무조건 내려와야하니, dp 값을 `dp[i-1][j] + map[i][j]`로 초기화 해준다.

 

2.  오른쪽으로 쭉 간다.

여기부터 기존의 DP랑 좀 다르다. 우선 오른쪽으로 쭉 갔을 경우의 값을 별도로 저장할 수 있도록 `leftToRight` 배열을 만든다. 

// -> 방향으로 전진할 때 갱신
int [] leftToRight = new int[M];
leftToRight[0] = dp[i][0];
for(int j=1; j<M; j++){
    // 여기서 멈추거나, 여기까지 전진해오거나
    leftToRight[j] = Math.max(dp[i][j], leftToRight[j-1] + map[i][j]);
}

여기서 목표는 `leftToRight[j]`값에 최대값을 갱신하는 것이다. 그러므로 최대이익의 경우를 따져봐야 한다.

왼쪽에서 오던 칸을 받을 것인지, 받지 않을 것인지 선택한다. 굳이 더 높은 값이 아니라면 위에서 아래온 내려온 값을 선택한다.

 

3. 왼쪽으로 쭉 간다.

마찬가지로 왼쪽으로 쭉 갔을 경우의 값을 저장할 수 있도록 별도의 배열을 선언한다.

// <- 방향으로 전진할 때 갱신
int [] rightToLeft = new int[M];
rightToLeft[M-1] = dp[i][M-1];
for(int j=M-2; j>=0; j--){
    // 여기서 멈추거나, 여기까지 전진해오거나
    rightToLeft[j] = Math.max(dp[i][j], rightToLeft[j+1] + map[i][j]);
}

 

 

그리고 중요한 것은, 두 배열 중 최대값으로 갱신해주는 것이다.

for(int j=0; j<M; j++){
    dp[i][j] = Math.max(leftToRight[j], rightToLeft[j]);
}

 

이로써 i층까지의 탐색이 완료됐다. 각 dp[i][j]칸에는 중복을 방문하지 않으면서 현재 칸에서 얻을 수 있는 최대 이익이 저장된다.

 

 

4. 전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main{

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int [][] map = new int[N][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());
            }
        }

        int [][] dp = new int[N][M];
        // 1층 초기화
        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++){
            // 위에꺼 밑으로 그대로 전달
            for(int j=0; j<M; j++){
                dp[i][j] = dp[i-1][j] + map[i][j];
            }

            // -> 방향으로 전진할 때 갱신
            int [] leftToRight = new int[M];
            leftToRight[0] = dp[i][0];
            for(int j=1; j<M; j++){
                // 여기서 멈추거나, 여기까지 전진해오거나
                leftToRight[j] = Math.max(dp[i][j], leftToRight[j-1] + map[i][j]);
            }
_
            // <- 방향으로 전진할 때 갱신
            int [] rightToLeft = new int[M];
            rightToLeft[M-1] = dp[i][M-1];
            for(int j=M-2; j>=0; j--){
                // 여기서 멈추거나, 여기까지 전진해오거나
                rightToLeft[j] = Math.max(dp[i][j], rightToLeft[j+1] + map[i][j]);
            }

            for(int j=0; j<M; j++){
                dp[i][j] = Math.max(leftToRight[j], rightToLeft[j]);
            }
        }

        System.out.println(dp[N-1][M-1]);
    }

}