[백준] 2169 로봇 조종하기

문제보기

보통 이런문제는 아래 & 우측으로 가는 이동만 가능해서 2차원 배열만 써도 충분히 dp로 풀이가 가능하다.
다만 이 문제는 아래 & 우측 & 좌측 이 세가지 방향이 모두 가능하기 때문에 이차원 배열만으로는 충분히 경우의 수를 가늠할 수 없다.
따라서 arr[n][m][3] 이런 배열을 만들어서, 맨 마지막 인덱스가 0일때는 위에서 내려온 경우의 최대 가치, 1일때는 좌에서 우로 넘어온 경우의 최대 가치, 2일때는 우에서 좌로 넘어온 최대 가치라고 생각하면서 만들어줘야한다.
자세한 내용은 주석으로!

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

class Main{
	
	static int ip(String s){ return Integer.parseInt(s); };

     public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int n = ip(st.nextToken());
    	int m = ip(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] = ip(st.nextToken());
    		}
    	}
    	
		// 이 배열의 마지막 인덱스는 진행되어 내려온 방향을 의미한다.
		// 0 : 위->아래 , 1 : 좌 -> 우 , 2 : 우 -> 좌
    	int[][][] temp = new int[n][m][3];
    	int[][] d = new int[n][m]; // 위의 배열을 모두 종합하여 세 경우 중 가장 큰값을 저장한다 
    	d[0][0] = map[0][0]; // 시작 지점
		// 첫 행은 오직 좌 -> 우 밖에 최대 가치를 만들 방법이 없다.
    	for(int j = 1 ; j < m ; j++) {
    		d[0][j] = d[0][j-1] + map[0][j];
    	}
		// 두번째 행부터 계산해보자 
    	for(int row = 1 ; row < n ; row++) {
			// 위 -> 아래로 내려온 경우 : 위에다가 현재값을 더한다 
    		for(int j = 0 ; j < m ; j++) {
    			temp[row][j][0] = d[row-1][j] + map[row][j]; 
    		}
			// 좌 -> 우로 이동한 경우. 단, 첫 열은 좌에서 넘어오는것이 불가능하므로 그냥 위에서 갖고온다
    		temp[row][0][1] = d[row-1][0] + map[row][0];
    		for(int j = 1 ; j < m ; j++ ) {
				// 왼쪽에 있는 최대값에서 좌->우로 넘어온 최댓값과 위->아래로 넘어온 최댓값 중 더 큰것을 선택해서 이동한다
    			temp[row][j][1] = Math.max(temp[row][j-1][1], temp[row][j-1][0]) + map[row][j];
    		}
    		// 우-> 좌로 이동한 경우도 마찬가지로 진행한다
    		temp[row][m-1][2] = d[row-1][m-1] + map[row][m-1];
    		for(int j = m-2 ; j >= 0 ; j-- ) {
    			temp[row][j][2] = Math.max(temp[row][j+1][0], temp[row][j+1][2]) + map[row][j];
    		}
			// 마지막으로 d 배열에 세 경우 중 큰 값을 골라서 저장한다
    		for(int j = 0 ; j < m ; j++) {
    			d[row][j] = Math.max(temp[row][j][0], Math.max(temp[row][j][1], temp[row][j][2]));
//        		System.out.println("위 : " + temp[row][j][0] + " 왼 : " + temp[row][j][1] + " 오 : " + temp[row][j][2] + " 최대 : " + d[row][j]);
    		}
    	}
    	System.out.println(d[n-1][m-1]);
     }
}