백준_로봇 조종하기_2169[Java]

문제

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

2169번: 로봇 조종하기

 

풀이

* 문제 이해

1. 동 서 남으로 이동 가능하나 북으로는 이동 불가능 

2. 재탐사 불가능 

3. 끝까지 도달했을 경우 가치 합이 최대여야 한다. 

 

이 문제도 DP로 해결할 수 있다. 

 

이동을 동서남으로만 가능하므로 현 위치에 도착하기 전의 위치는 현위치에서의 서동북이 되겠다.

mars[i][j]  현재 위치 : ( i, j )

                 가능한 이전 위치 :   서 ( i, j-1 ), 동 ( i, j+1 ), 북 ( i-1, j )

DP[i][j]이 최대의 숫자를 갖기 위해서는 현재 위치 + Max(DP[i-1][j], DP[i,j-1], DP[i,j+1]) 

i와 j를 1부터 시작하여 오른쪽으로 한칸씩 이동시키며 계산하는 이중 for문을 이용하면 될 것 같다.

 

하지만 이렇게 단순하게 생각하면 문제가 발생한다.

오른쪽으로 이동하는 for문 덕분에 오른쪽에서 왼쪽으로 이동하는 경우의 계산이 힘들기 때문이다.

예를 들어, i = 2, j = 2인 경우 위에서 오거나 왼쪽에서 오는 경우에는 계산이 가능하지만 오른쪽에서 오는 경우의 계산이 불가능하다.  

 

따라서 해당 위치의 최댓값을 구하기 위해서는 (왼쪽 -> 오른쪽),  (왼쪽 <- 오른쪽)  이렇게 두 가지 방향의 값들을 먼저 구해야 한다.

따라서 이 두 가지 방향의 값들을 구해 임시로 저장하는 배열이 따로 필요하다. (temp[][])

나는 temp[0][j] 를 왼쪽에서 오른쪽으로 이동했을 때의 값

       temp[1][j]를 오른쪽에서 왼쪽으로 이동했을 때의 값을 넣었다.

이 둘 중 최댓값이 dp[i][j]의 값이 되는 것이다. 

 

 

* 주의점

- 초기화 1 : DP[1][1] = mars[1][1]

- 초기화 2 : i = 1 일때는 왼쪽에서 오른쪽 이동만 가능, 따라서 미리 초기화해준다. !

- j = 1 일때는 위쪽에서 아래쪽, 오른쪽에서 왼쪽 이동만 가능하다는 것을 주의한다. 

  temp[0][0] 와 temp[1][M+1]을 초기화하는 이유

 

 

코드

 

import java.util.Scanner;

public class Main {
	static int N,M;
	static int[][] mars;
	static int[][] dp;
	static int[][] temp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		mars = new int[N+1][M+1];
		dp = new int[N+1][M+1];
		temp = new int[2][M+2];
		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= M; j++){
				mars[i][j] = sc.nextInt();
			}
		}
		
		dp[1][1] = mars[1][1];
		
		for(int j = 2; j <= M; j++) dp[1][j] = mars[1][j]+ dp[1][j-1];
		
		for(int i = 2; i <= N; i++) {
			
			temp[0][0] = dp[i-1][1];
			for(int j = 1; j <= M; j++) {
				temp[0][j] = Math.max(temp[0][j-1], dp[i-1][j])+ mars[i][j];
			}
			
			temp[1][M+1] = dp[i-1][M];
			for(int j = M; j >= 1; j--) {
				temp[1][j] = Math.max(temp[1][j+1], dp[i-1][j]) + mars[i][j];
			}
			
			for(int j = 1; j <= M; j++) {
				dp[i][j] = Math.max(temp[0][j], temp[1][j]);
			}
		}
		System.out.println(dp[N][M]);
		
		sc.close();
	}

}

 

참고

- 조건문 참고 / 생각의 흐름 설명 잘해주심 !

https://blog.naver.com/occidere/220808155184

[백준] 2196 - 로봇 조종하기