[BOJ 2169] 로봇 조종하기 (Java)

BOJ 2169 로봇 조종하기

문제풀이

최악의 경우에 N, M이 1000이 될 수 있기 때문에 주어진 제약조건에서 탐색 알고리즘을 통한 완전 탐색은 불가능하다. 따라서 각 칸에 도착하는 최댓값을 갱신해나가는 다이나믹프로그래밍을 사용해야한다.

• 각 칸에 도착할 수 있는 경우를 잘 구분하여 규칙을 찾아내는 것이 중요하다.
  • 첫 행은 왼쪽에서 오른쪽으로만 갈 수 있다.
  • 첫 열에서는 위, 오른쪽에서 올 수 있고 마지막 열은 위, 왼쪽에서 올 수 있다.
  • 나머지는 위, 오른쪽, 왼쪽에서 올 수 있다.
• 세 방향에서 오는 경우를 동시에 비교해야한다.
  • DP 테이블을 왼쪽에서 오른쪽으로 갱신해나갈 경우 오른쪽에서 오는 경우는 갱신되지 않은 값들로 비교를 하게된다.
  • 따라서 임시 배열을 만들어 왼쪽에서 오른쪽, 오른쪽에서 왼쪽의 경우를 저장하고 그 후 최댓값을 갱신해야한다.

구현코드

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

public class Main {
	
	static int[][] map;
	static int[][] dp;
	static int N, M;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		
		map = new int[N][M];
		dp = new int[N][M];
		
		for(int r = 0 ; r < N ; ++r) {
			st = new StringTokenizer(br.readLine());
			for(int c = 0 ; c < M ; ++c) {
				int num = stoi(st.nextToken());
				if(r == 0) dp[r][c] = num;
				map[r][c] = num;
			}
		}
		
		// DP 가장 윗 행 초기화
		for(int c = 1 ; c < M ; ++c) {
			dp[0][c] += dp[0][c - 1]; 
		}
		
		// DP 중간 행 갱신 
		for(int r = 1 ; r < N ; ++r) {
			int[][] temp = new int[2][M];
			
			// 왼쪽에서 오른쪽의 경우 
			// 가장 왼쪽 칸 초기화 (위에서 내려온) 
			temp[0][0] = map[r][0] + dp[r - 1][0];
			for(int c = 1 ; c < M ; ++c) {
				temp[0][c] = Math.max(temp[0][c - 1], dp[r - 1][c]) + map[r][c];
			}
			
			// 오른쪽에서 왼쪽의 경우
			// 가장 오른쪽 칸 초기화 (위에서 내려온)
			temp[1][M - 1] = map[r][M - 1] + dp[r - 1][M - 1];
			for(int c = M - 2 ; c >= 0 ; --c) {
				temp[1][c] = Math.max(temp[1][c + 1], dp[r - 1][c]) + map[r][c];
			}
			
			// 왼쪽에서 오른쪽과 오른쪽에서 왼쪽의 두 경우중 큰 것으로 DP 갱신 
			for(int c = 0 ; c < M ; ++c) {
				dp[r][c] = Math.max(temp[0][c], temp[1][c]);
			}
		}

		System.out.println(dp[N - 1][M - 1]);
	}
	
	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}