11048 이동하기

1. 풀이

 

문제 예시 1로 설명하겠다.

 

3 4
1 2 3 4
0 0 0 5
9 8 7 6

 

map 배열에 각 위치의 사탕 개수를 입력한다.

 

즉,

1 2 3 4
0 0 0 5
9 8 7 6

 

이 값들을 map 배열에 입력한다.

 

문제에서 한 점은 1) 오른쪽, 2) 아래쪽, 3) 오른쪽 아래로 이동 가능하다고 했다.

즉, (1,1) 위치에서 이동 가능한 곳은 아래 그림과 같다.

 

 

 

 

그렇기 때문에 위치(2,2)에 있는 준규가 가질 수 있는 사탕 개수의 최댓값은 

(2,2) 위치의 사탕 개수  + (1,1), (1,2), (2,1) 위치 사탕 개수 중 제일 큰 값이다.

 

자세히 설명하자면,

(1,1) 에서 오른쪽, 아래쪽, 오른쪽 아래 방향으로 이동 가능하다. 그런데 이것은 출발지 -> 도착지 방향이다.

그렇다면 도착지에서 출발지를 바라보는 방향은 이와 반대로 왼쪽, 위쪽, 왼쪽 위 방향이 된다.

그래서 (2,2) 로 오기 전의 위치는 (2,1), (1,2), (1,1) 이다.

 

 

이를 이용해서 최대 사탕 개수를 구하려면 아래와 같은 식을 사용하면 된다.

 

dp[i][j] = map[i][j] + Math.max(Math.max(dp[i-1][j-1], dp[i-1][j]) , dp[i][j-1])

 

 

 

 

2. 최종 코드

 

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

public class Main {
	
	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 map[][] = new int[N+1][M+1];
		int dp[][] = new int[N+1][M+1];
		
		for(int i= 1; i<=N; i++) {
			st = new StringTokenizer(br.readLine(), " " );
			for(int j=1; j<=M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		
		for(int i=1; i<=N; i++) {
			for(int j =1; j<=M;j++ ) {
				dp[i][j] = map[i][j] + Math.max(Math.max(dp[i-1][j-1], dp[i-1][j]) , dp[i][j-1]); 
			}
		}
		
		System.out.println(dp[N][M]);
	}
}