백준 14430번: 자원 캐기

문제 설명

• https://www.acmicpc.net/problem/14430
• 로봇은 오른쪽 또는 아래로만 이동할 수 있습니다. 로봇이 (1,1)에서 (N,M)으로 이동하면서 모을 수 있는 자원의 최댓값을 구하는 문제입니다.

접근법

• 로봇은 오른쪽 또는 아래로만 이동할 수 있다.는 말은 (i,j)위치는 (i-1,j)또는 (i,j-1)에서만 접근이 가능하다는 말과 동일합니다.
• 로봇이 (1,1)에서 (i,j)까지 오면서 모은 자원은 (i-1,j)까지 오면서 모은 자원 or (i,j-1)까지 오면서 모은 자원 중 큰 값 + (i,j)에 존재하는 자원과 같습니다.

정답

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

public class Main {
	static int[] dx = {-1,0};
	static int[] dy = {0,-1};
	public static void main(String[] args) throws Exception{
		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[][] board = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				int left = (j-1<0)?0:board[i][j-1];
				int up = (i-1<0)?0:board[i-1][j];
				board[i][j] += Math.max(left,up);
			}
		}		
		System.out.println(board[N-1][M-1]);
	}
}