[백준 / BOJ] 17484번 : 진우의 달 여행 (Small) - JAVA

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

17484번: 진우의 달 여행 (Small)

다이나믹 프로그래밍

cost 배열에는 한 칸에 3개의 값을 저장하도록 했다. 오른쪽에서 왔을 때, 왼쪽에서 왔을 때, 그리고 직진했을 때의 연료 양의 합이다.

 

1. right : (i - 1, j + 1)에서 대각선으로 올 때
2. left : (i - 1, j - 1)에서 대각선으로 올 때
3. straight : (i - 1, j)에서 직진해서 올 때

 

연속으로 같은 방향을 선택할 수 없기 때문에, (i, j)칸에서의 연료양을 다음과 같이 계산했다.

if(j - 1 >= 0) {
    left = road[i][j] + Math.min(cost[i - 1][j - 1].straight, cost[i - 1][j - 1].right);
}

if(j + 1 < M) {
    right = road[i][j] + Math.min(cost[i - 1][j + 1].left, cost[i - 1][j + 1].straight);
}

straight = road[i][j] + Math.min(cost[i - 1][j].left, cost[i - 1][j].right);

left를 계산하기 위해 (i - 1, j - 1)에서 선택할 수 있는 연료 양은 straight와 right 둘 중 하나이다. left를 선택한다면 2연속 같은 방향이기 때문이다.

 

같은 이유로 right를 계산하기 위해 선택할 수 있는 연료 양은 left와 straight 둘 중 하나이고, straight를 계산하기 위해 선택할 수 있는 연료 양은 left와 right 둘 중 하나이다.

 

조건문을 최소화하고 비교만 하고 싶어서 만일 옆에 칸이 없다거나, 혹은 같은 방향이어서 left, straight, right 중 채울 수 없는 값이 있다면 Integer.MAX_VALUE로 두게 했다. 

 

전체 코드

// 시간 : 84ms
// 메모리 : 11776KB
public class Main {

	static class Node {
		int right;
		int straight;
		int left;
		
		public Node(int right, int straight, int left) {
			super();
			this.right = right;
			this.straight = straight;
			this.left = left;
		}
	}
	
	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[][] road = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				road[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		Node[][] cost = new Node[N][M];
		
		for (int i = 0; i < M; i++) {
			int left = Integer.MAX_VALUE;
			int right = Integer.MAX_VALUE;
			int straight = road[0][i] + road[1][i];
			
			if(i - 1 >= 0) left = road[0][i - 1] + road[1][i];
			if(i + 1 < M) right = road[0][i + 1] + road[1][i];
			
			cost[1][i] = new Node(right, straight, left);
		}
		
		for (int i = 2; i < N; i++) {
			for (int j = 0; j < M; j++) {
				int left = Integer.MAX_VALUE;
				int right = Integer.MAX_VALUE;
				int straight = Integer.MAX_VALUE;
				
				if(j - 1 >= 0) {
					left = road[i][j] + Math.min(cost[i - 1][j - 1].straight, cost[i - 1][j - 1].right);
				}
				
				if(j + 1 < M) {
					right = road[i][j] + Math.min(cost[i - 1][j + 1].left, cost[i - 1][j + 1].straight);
				}
				
				straight = road[i][j] + Math.min(cost[i - 1][j].left, cost[i - 1][j].right);
				
				cost[i][j] = new Node(right, straight, left);
			}
		}
		
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < M; i++) {
			min = Math.min(min, cost[N-1][i].left);
			min = Math.min(min, cost[N-1][i].right);
			min = Math.min(min, cost[N-1][i].straight);
		}
		
		System.out.println(min);
	}

}