[JAVA] 백준 11048 - 이동하기

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

11048번: 이동하기

 

🤔 문제 풀이

dp 문제 치곤 굉장히 쉬운 문제였다.

 

문제에서 이동할 수 있는 방향은 자기 자신을 기준으로 x+1 or y+1 or x+1, y+1 만 존재한다.

나는 먼저 map배열을 생성하여 좌표 별 사탕 개수 정보를 입력 받았고

dp 배열을 생성하여 현재 좌표에서 dp 배열 x-1, y  and  x, y-1 and x-1, y-1  좌표 값들의 최대 값을 구하고

현재 좌표에서 가져갈 수 있는 사탕 개수를 더해 각 좌표별 가져갈 수 있는 최대 사탕 개수를 갱신해주었다.

 

import java.io.*;
import java.util.*;

public class Main {
	static int[][] map;
	static int[][] dp;
	static int n,m;
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		map = new int[n+1][m+1];
		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] = Math.max(dp[i-1][j], Math.max(dp[i][j-1], dp[i-1][j-1]))
						+ map[i][j];
			}
		}
		
		System.out.println(dp[n][m]);
			
	}
}