백준 2169 : 로봇 조종하기

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

2169번: 로봇 조종하기

[ 문제풀이 ]

처음에는 dfs + dp로 풀었는데 중복 방문 부분을 놓쳐서 TLE가 발생하였다. 해결하려고 하였지만 자꾸 실패해서 dp로 해결하였다.

왼쪽, 오른쪽, 아래쪽으로만 로봇이 움직일 수 있다는 조건을 잘 생각해보면 같은 높이에서는 절대로 좌/우측을 번갈아서 이동할 수 없다는 것을 알 수 있다. 따라서 dp 테이블을 다음과 정의하자.

dp[0][i][j] : (i, j) 최댓값
dp[1][i][j] : 우측, 아래로 이동했을때의 (i, j) 최댓값
dp[2][i][j] : 좌측, 아래로 이동했을때의 (i, j) 최댓값

 

dp[0][i][j]에 (0,0)에서 올 수 있는 최댓값이 저장되어있다고 가정한다면 dp[1][i+1][j]에는 i행에서 오른쪽, 아래쪽으로만 이동했을 때 해당 (i+1, j)에 갈 수 있는 최댓값이 저장될 것이고, dp[2][i+1][j]에는 i행에서 왼쪽, 아래쪽으로만 이동했을 때 해당 (i+1, j)에 갈 수 있는 최댓값이 저장될 것이다.

두 경우에서 최댓값이 (0, 0)에서 (i+1, j)까지 갈 수 있는 최댓값일 것이다.

다만, (0,0)에서 시작하기 때문에 초기에는 오른쪽으로만 이동할 수 있다. 따라서 초기값을 따로 설정해준다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static int[][] map;
	static int[][][] dp;

	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			dp = new int[3][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());
				}
			}

			/**
			 * dp[0][i][j] : (i,j) 최댓값
			 * dp[1][i][j] : 우측, 아래로 이동했을때의 (i,j) 최댓값
			 * dp[2][i][j] : 좌측, 아래로 이동했을때의 (i,j) 최댓값
			 */
			for (int i = 0; i < M; ++i) {
				for (int j = 0; j < 3; ++j) {
					if (i == 0) dp[j][0][i] = map[0][i];
					else dp[j][0][i] = dp[j][0][i-1] + map[0][i];
				}
			}

			for (int i = 1; i < N; ++i) {
				for (int j = 0; j < M; ++j) {
					if (j == 0) dp[1][i][j] = dp[1][i-1][j] + map[i][j];
					else dp[1][i][j] = Math.max(dp[1][i-1][j], dp[1][i][j-1]) + map[i][j];
				}

				for (int j = M-1; j >= 0; --j) {
					if (j == M-1) dp[2][i][j] = dp[2][i-1][j] + map[i][j];
					else dp[2][i][j] = Math.max(dp[2][i-1][j], dp[2][i][j+1]) + map[i][j];
				}

				for (int j = 0; j < M; ++j) {
					dp[0][i][j] = Math.max(dp[1][i][j], dp[2][i][j]);
					dp[1][i][j] = dp[2][i][j] = dp[0][i][j];
				}
			}
			bw.write(dp[0][N-1][M-1] + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}