[백준/자바] 11048번: 이동하기

문제

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

풀이

• N*M 미로
• 각 방에는 사탕이 놓여짐
• (1, 1)에서 (N, M)으로 이동
• (r+1, c), (r, c+1), (r+1, c+1)로 이동 가능
• 각 방에 방문할 때마다 사탕 획득
• 가져올 수 있는 사탕 개수의 최댓값 출력

메모이제이션을 활용한 이전 글과 매우 유사한 DP 문제입니다.

3방향으로 이동을할 수 있으니, 현재 좌표에서 3가지의 이전 좌표의 값들 중 최댓값을 더하며 이동하면 됩니다.

코드

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

public class Main {
	static int n, m;
	static int[][] map, dp;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
        // 지도 초기화
		map = new int[n+1][m+1];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
        // DP
		dp = new int[n+1][m+1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
            	// 현재 값 + 이전 값들 중 최댓값
				dp[i][j] = map[i][j] + Math.max(dp[i-1][j], Math.max(dp[i][j-1], dp[i-1][j-1])); 
			}
		}
		
		System.out.println(dp[n][m]);
	}
}