[BOJ] 백준 11048 - 이동하기 (자바)

DP?

dp 문제인가?

아주 기초적인 dp 문제인듯

문제에 설명이 다 나와있다. 그냥 따라 하면 됨.

풀이

1. (1,1)칸 부터 위, 왼 ,위왼 중 가장 큰 값이랑 자기자신 값이랑 더하면 된다.

2. (N,M)까지 하면 arr[N][M] 이 정답이 된다.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
 
        int[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            str = br.readLine().split(" ");
            for (int j = 1; j <= m; j++) {
                arr[i][j] = Integer.parseInt(str[j-1]);
            }
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] += Math.max(arr[i][j-1],Math.max(arr[i-1][j], arr[i-1][j-1]));
            }
        }
        System.out.println(arr[n][m]);
    }
}