99클럽 코테 스터디 25일차 TIL [DP]

- 오늘의 학습 키워드 : DP

[문제 이름 : 로봇 조종하기 (백준, G2)]
문제 url : https://www.acmicpc.net/problem/2169

내가 작성한 코드는 아래와 같다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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];
        dp[0][0] = map[0][0];

        // 1. 이미 방문한 곳은 방문할 수 없으므로, 0행은 오른쪽으로만 이동 가능
        for (int i = 1; i < M; i++) {
            dp[0][i] = dp[0][i-1] + map[0][i];
        }

        // 2. 각 행에 대해 계산
        for (int i = 1; i < N; i++) {
            // 2.(1) 왼쪽에서 오는 경우
            int[] left = new int[M];
            left[0] = dp[i-1][0] + map[i][0];
            for (int j = 1; j < M; j++) {
                left[j] = Math.max(left[j-1], dp[i-1][j]) + map[i][j];
            }

            // 2.(2) 오른쪽에서 오는 경우
            int[] right = new int[M];
            right[M-1] = dp[i-1][M-1] + map[i][M-1];
            for (int j = M-2; j >= 0; j--) {
                right[j] = Math.max(right[j+1], dp[i-1][j]) + map[i][j];
            }

            // 3. 현재 행의 dp 계산
            for (int j = 0; j < M; j++) {
                dp[i][j] = Math.max(left[j], right[j]);
            }
        }

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

풀이 과정(풀이 시간 : 45분)

DP 문제인 것은 알았으나, 접근을 어떻게 해야 하는지에 대해 고민을 많이 했다.

1. 한 번 방문한 곳은 다시 방문이 불가하므로, 0행은 오른쪽으로만 이동할 수 있다. 이에 대한 코드를 먼저 작성한다.

2. 이후 각 행을 순회하며 DP에 값을 어떻게 배치할지를 계산한다. dp[i][j]는 (i, j) 위치까지 탐사했을 때 얻을 수 있는 최대 탐사 가치를 의미한다.

2.(1) 왼쪽에서 오른쪽으로 이동하는 경우와, 위에서 아래로 이동하는 경우를 left[] 배열에 저장한다.
2.(2) 오른쪽에서 왼쪽으로 이동하는 경우와, 위에서 아래로 이동하는 경우를 right[] 배열에 저장한다.
3. 현재 dp값을 2.(1), 2.(2)에서 계산된 left, right중 큰 값으로 갱신한다.

내일은 하반기 자기소개서를 첨삭하고, 문제가 무엇인지 분석해보고자 한다.