[백준 java] 11048 - 이동하기

11048번: 이동하기

DP가 아닌 BFS를 사용하여 최대값을 구하도록 풀어도 봤는데 메모리초과와 시간 초과가 떴다...

---

 

 

입력받은 숫자들을 2차원 int배열에 넣고

해당 배열을 사용하여 dp[i][j]의 값을 구한다.

 

dp[i][j-1] 와 dp[i-1][j] 의 값을 비교하여 dp[i][j]를 구한다.

 

만약 b[1][2]의 총 최대값을 구하려면 b[0][2]와 b[1][1] 을 비교하여 큰 값을 b[1][2]과 더하여 dp에 저장한다.

이것을 dp[N][M]까지 반복하여 계산하면 사탕수의 최대값을 구할 수 있다.

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B11048 {
    static int N,M;
    static int[][] board;
    static int[][] 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());

        board = new int[N+1][M+1];
        dp =  new int[N+1][M+1];

        for (int i = 1; i < N+1; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for (int j = 1; j < M+1; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        calc();
    }

    private static void calc() {

        for (int i = 1; i < N+1; i++) {
            for (int j = 1; j < M+1; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + board[i][j];
            }
        }
        System.out.println(dp[N][M]);
    }
}