백준 11048번 이동하기

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

11048번: 이동하기

 

• 풀이

준규의 이동 경로는 오른쪽, 아래, 오른쪽 아래 대각선으로 총 세 가지이다.

오른쪽 아래 대각선은 오른쪽, 아래나 아래, 오른쪽으로 이동할 수 있어 값이 작거나 같기 때문에 고려하지 않아도 된다.

 

예제를 표로 그려보면 다음과 같다.

왼쪽은 그래프, 오른쪽은 dp그래프를 표현한 표이다.

dp [N][M]은 현재의 위치(N, M)에 도달하기까지 최대 값을 의미한다.

예를 들어, DP[2][3]의 값(18)은 graph [2][3] 값(8)에 DP [2][3] 기준으로 왼쪽 값(10)과 위쪽 값(3) 중 최댓값(10)을 더하면 된다.

즉, dp[N][M] = graph [N][M] + Math.max(Math.max(dp [N-1][M], dp [N][M-1]))이다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Vector;

public class Main {
	public static void main(String[] args) {
		int max=0;
		
		Scanner s = new Scanner(System.in);
		
		//System.out.println("미로의 크기를 입력하시오: ");
		int N = s.nextInt();
		int M = s.nextInt();
		
		
		int graph[][] = new int[N+1][M+1];
		int dp[][] = new int[N+1][M+1];
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=M;j++) {
				graph[i][j] = s.nextInt();
			}
		}
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=M;j++) {
				dp[i][j]=graph[i][j]+Math.max(dp[i-1][j],dp[i][j-1]);
			}
		}

		System.out.println(dp[N][M]);
	}
}