[Java] 백준 2169번: 로봇 조종하기

[문제 바로 가기] - 로봇 조종하기

📌 유형 : dp

최근에 본 기업 코딩테스트 3번 문제와 아주 유사한 문제로 코딩테스트에서는 DFS로 탐색했는데 시간 초과가 났다. 해당 문제는 N과 M이 최대 200까지였음에도 2초를 넘어갔으므로 이 문제에서도 당연히 시간초과가 날 것이다.

💡 아이디어

따라서 이 문제는 dp로 풀이해야 한다.

로봇은 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있으므로 dp 배열을 방향까지 포함한 3차원 배열로 선언했다.

dp[i][j][0] : 왼쪽 방향에서 오는 경우
dp[i][j][1] : 위쪽 방향에서 오는 경우
dp[i][j][2] : 오른쪽 방향에서 오는 경우

따라서 점화식을 세우면 다음과 같다.

1. 왼쪽 방향에서 오는 경우 : dp[i][j][0]

Math.max(dp[i][j - 1][0], dp[i][j - 1][1])
dp[i][j - 1][2]는 이미 dp[i][j][2]에서 왔으므로 이 경우를 포함하면 안 된다.

2. 위쪽 방향에서 오는 경우 : dp[i][j][1]

Math.max(dp[i - 1][j][0], Math.max(dp[i - 1][j][1], dp[i - 1][j][2]))

3. 오른쪽 방향에서 오는 경우 : dp[i][j][2]

Math.max(dp[i][j + 1][1], dp[i][j + 1][2])
dp[i][j + 1][0]도 이미 dp[i][j][0]에서 왔기 때문에 이 경우는 제외한다.

---

풀이

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

/**
 * 백준 2169번 로봇 조종하기
 * - dp
 */
 
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 + 1][M + 1];
		int[][][] dp = new int[N + 1][M + 1][3];
		
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = -101 * N * M;
			}
		}
		
		dp[1][1][0] = dp[1][1][1] = dp[1][1][1] = map[1][1];
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (i > 1) dp[i][j][1] = Math.max(dp[i - 1][j][0], Math.max(dp[i - 1][j][1], dp[i - 1][j][2])) + map[i][j];
				if (j > 1) dp[i][j][0] = Math.max(dp[i][j - 1][0], dp[i][j - 1][1]) + map[i][j];
			}
			
			for (int j = M - 1; j >= 1; j--) {
				dp[i][j][2] = Math.max(dp[i][j + 1][1], dp[i][j + 1][2]) + map[i][j];
			}
		}
		
		System.out.println(Math.max(dp[N][M][0], dp[N][M][1]));
	}
}