[백준] 11048번 : 이동하기- JAVA [자바]

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

11048번: 이동하기

---

문제

 

이 문제는 DP의 Memonization을 이용하여 풀었다.

 

문제는 간단하다 (1, 1) 좌표에서 시작하여 (N, M) 좌표까지 이동하면서 사탕을 먹으면서 간다.

방향은 3가지로 아래, 오른쪽, 오른쪽 아래 대각선을 이동할 수 있다.

 

DP의 기본적인 문제라고 생각한다. 왜냐하면 특별한 점화식이 필요없기 때문이다

 

나의 로직은 아래와 같다.

(1, 1) 좌표에서 내가 갈 수 있는 다음 좌표에대해서, 내가 갈 DP 배열에 저장되어있는 값이 큰지 아니면 현재 나의 DP 배열에 저장되어 있는 값 + 다음 위치에 있는 사탕 수가 큰지를 비교하여 더 큰 수를 내가 갈 DP 배열에 저장하면 끝이다.

 

이러한 점화식이 없고 방향만을 이동하면서 최대값을 요구하는 알고리즘 문제가 많기 때문에 자세한 설명은 건너띄도록 하겠다.

 

아래의 Memonization 수법을 사용하는 코드가 핵심이다.

// 만약 다음으로 갈 수 있다면. 
if(isPossible(nextX, nextY)) {
	// 핵심코드.
	dp[nextY][nextX] = Math.max(dp[nextY][nextX], dp[i][j] + map[nextY][nextX]);
}

---

전체 코드

public class Main {
	static int N, M;
	static int[][] map;
	
	public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("input.txt"));
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	StringTokenizer st;
    	
    	st = new StringTokenizer(in.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	map = new int[N][M];
    	int[][] dp = new int[N][M];
    	
    	for(int i = 0; i < N; i++) {
    		st = new StringTokenizer(in.readLine());
    		for(int j = 0; j < M; j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	dp[0][0] = map[0][0];
    	
    	int[][] dir = {{0, 1}, {1, 0}, {1, 1}};
    	
    	//DP를 이용한 풀이 시작. 
    	for(int i = 0; i < N; i++) {
    		for(int j = 0; j < M; j++) {
    			int cnt = map[i][j];
    			
    			for(int d = 0; d < 3; d++) {
    				int nextX = j + dir[d][0];
    				int nextY = i + dir[d][1];
    				
    				if(isPossible(nextX, nextY)) {
    					dp[nextY][nextX] = Math.max(dp[nextY][nextX], dp[i][j] + map[nextY][nextX]);
    				}
    			}
    		}
    	}
    	
    	
    	System.out.println(dp[N - 1][M - 1]);
    }
	
	static boolean isPossible(int x, int y) {
		if(x >= M || x < 0 || y < 0 || y >= N) 
			return false;
		
		return true;
	}
}

 

---

결과