링크

11048 이동하기

문제

풀이

이 문제는 DP문제로 오른쪽, 아래, 오른쪽 아래 대각선으로 이동할 수 있는데 그 중 최대값을 뽑아내는 것이다.

이동할때마다 이동하기전의 누적값 + 이동할 좌표의 값과 이동할 좌표의 누적값을 비교해서 큰 값을 계속 갱신해주면 된다.
이를 점화식으로 나타내면 아래와 같다.

dp[newX][newY] = Math.max(dp[newX][newY], dp[x][y] + map[newX][newY])

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] arr = br.readLine().split(" ");
		int n = Integer.parseInt(arr[0]);
		int m = Integer.parseInt(arr[1]);
		
		int[][] map = new int[n][m];
		int[][] dp = new int[n][m];
		int[] dx = {0, 1, 1};
		int[] dy = {1, 0, 1};
		
		for(int i=0;i<n;i++) {
			arr = br.readLine().split(" ");
			
			for(int j=0;j<arr.length;j++) {
				map[i][j] = Integer.parseInt(arr[j]);
			}
//			System.out.println(Arrays.toString(map[i]));
		}
		
		dp[0][0] = map[0][0];
		
		for(int i=0;i<dp.length;i++) {
			
			for(int j=0;j<dp[i].length;j++) {
				
				for(int k=0;k<3;k++) {
					int newX = i + dx[k];
					int newY = j + dy[k];
//					System.out.println("newX = " + newX + ", newY = " + newY);
					
					if(newX < 0 || newY < 0 || newX >= map.length || newY >= map[0].length) continue;
					
					dp[newX][newY] = Math.max(dp[newX][newY], dp[i][j] + map[newX][newY]);
				}
			}
			
		}
		
		
		
//		for(int i=0;i<map.length;i++) System.out.println(Arrays.toString(dp[i]));
		System.out.println(dp[n-1][m-1]);
		
	}	
	
}