14430 : 자원 캐기 ( 백준 / java )

 

*해결 과정

오른쪽과 아래쪽만 이동하는 것에 유의하여 최대탐색 할 수 있는 숫자를 구하는 것이다. 그렇다면, BFS, DFS의 접근이 아니라 DP의 접근을 하는 것이 딱 눈에 띈다. 행이 0일때와, 열이 0일 때 2가지 경우를 나누어 먼저 초기 작업을 하고 이후에 (1,1)부터 왼쪽과 위쪽 값 중에 큰 값을 자신과 더하면서 업데이트하면 된다. 마지막으로 (N-1,M-1)의 숫자를 출력한다. 정형화 된 문제이다.

 

package bj;

import java.util.*;
public class Main {

	static int N;
	static int M;
	static int[][] array;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		array = new int[N][M];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				array[i][j] = sc.nextInt();
			}
		}
		
		for(int i=1;i<N;i++) {
			array[i][0] += array[i-1][0]; 
		}
		
		for(int j=1;j<M;j++) {
			array[0][j] += array[0][j-1];
		}
		
		for(int i=1;i<N;i++) {
			for(int j=1;j<M;j++) {
				array[i][j] += Math.max(array[i-1][j], array[i][j-1]); 
			}
		}
		System.out.println(array[N-1][M-1]);
	}

}