[백준11048] - 이동하기(JAVA)

[문제] 

출처 - https://www.acmicpc.net/problem/11048

11048번: 이동하기

---

[문제풀이] 

N*M 크기의 배열과 좌표가 주어졌으니 BFS, 나 DFS 로 푸는게 아닌가 생각이 들수도있지만 이문제는 DP문제이다.

준규가 이동할 수 있는 방향은  (r+1, c), (r, c+1), (r+1, c+1) 이다.

구하려고 하는 값은 이동 하면서 가져올 수 있는 사탕 개수의 최댓값을 구하기 때문에 점화식을

 

D[ x ][ y ] = x , y 지점에 도착했을 때 사탕을 가질 수 있는 최댓값 이라고 세울 수 있다.

 

어떻게 왔는지를 고민 하면 된다.

어느 한 지점 x, y 에 도착해있는데 해당 지점에 올 수 있는 경우는 이전 지점은 (x-1, y) , (x, y-1), (x -1, y -1) 이다. 

점화식을 이용하여 D[x-1][y] + Map[x][y] // (x-1, y 지점에 도착했을 때 가지는 사탕의 최댓값) + ( 도착한 지점의 사탕의 개수) 라는 식을  (x-1, y) , (x, y-1), (x -1, y -1)  이기 때문에 총 세개 만들 수 있다.

 

이중 최댓값을 가져야 하니 Max(D[x-1][y] , D[x][y-1], D[x-1][y-1]) + Map[x][y] 이다.

 

---

 

[소스코드] 

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

public class Main {
    public static void main(String[] args) throws IOException{
        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 d[][] = new int[n+1][m+1];
        int a[][] = 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++){
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                d[i][j] = Math.max(Math.max(d[i - 1][j - 1], (d[i - 1][j])), d[i][j - 1]) + a[i][j];
            }
        }

        System.out.println(d[n][m]);
    }
}