문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

풀이

주어진 N,M 크기의 배열을 선언하여 입력을 받는다. 맨 왼쪽위를 (1,1)이라 했을 때 (N,M)에 도착하면 얻을 수 있는 사탕의 최대를 구하면 된다.

입력을 받은 배열의 크기만큼 dp배열을 만들어서 값을 똑같이 넣어준다. 준규의 위치가 (r,c)라 했을 때 이동할 수 있는 방향이 (r+1, c) , (r, c+1), (r+1, c+1)이라고 문제에서 주어졌다.

따라서 방향에 맞춰서 최대치의 사탕의 갯수를 기록해주면 된다.

특정 위치에서 해당 위치의 최대값은 왼쪽에서 올 때, 왼쪽위에서 올때, 위에서 올 때의 갯수의 최대값을 넣어주면 된다.

for문을 배열의 크기만큼 돌리면서 left, up, leftUp의 값을 갱신해주면서 dp배열에 max(left, up, leftUp)의 값을 넣어준 뒤 dp[n-1][m-1]을 출력해주면 된다.

소스

import java.util.*;

public class Main {
	public static int m, n;
	public static int[][] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();

		int[][] map = new int[n][m];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		dp = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				dp[i][j] = map[i][j];
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int left, up, leftUp;

				if (i == 0) {
					leftUp = 0;
					up = 0;
				} else {
					leftUp = j == 0 ? 0 : dp[i - 1][j - 1];
					up = dp[i - 1][j];
				}

				if (j == 0) {
					left = 0;
				} else {
					left = dp[i][j - 1];
				}

				dp[i][j] = dp[i][j] + Math.max(left, Math.max(leftUp, up));
			}
		}

		System.out.println(dp[n - 1][m - 1]);

	}

}