백준 No.2169 로봇 조종하기

 

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

 

 

해당 문제는 2025년 상반기 엠로 코딩테스트 문제와 유사하였다.

처음엔 별 생각 없이, bfs로 접근하였는데, 이후에 dp로 푸는 문제라는 것을 깨달았다. 그러나, 최댓값을 구하는 과정에서 풀이 방식이 생각나지 않았다.

 

package _250320;

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

/**
 *packageName    : _250320
 * fileName       : BOJ_G2_2169_로봇조종하기
 * author         : moongi
 * date           : 3/21/25
 * description    :
 */
public class BOJ_G2_2169_로봇조종하기 {
	public static void main(String[] args) throws Exception {
		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[][] arr = new int[N][M];
		int[][] dp = new int[N][M];
		int[][] tmp = 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++) {

			// 왼쪽에서 오른쪽으로 오는 것
			tmp[0][0] = dp[i - 1][0] + arr[i][0];
			for (int j = 1; j < M; j++) {
				tmp[0][j] = Math.max(tmp[0][j - 1], dp[i - 1][j]) + arr[i][j];
			}

			// 오른쪽에서 왼쪽으로 오는 것
			tmp[1][M - 1] = dp[i - 1][M - 1] + arr[i][M - 1];
			for (int j = M - 2; j >= 0; j--) {
				tmp[1][j] = Math.max(dp[i - 1][j], tmp[1][j + 1]) + arr[i][j];
			}

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

		}

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

	}
}