[BOJ - JAVA] 11048 - 이동하기(DP)

# 주소

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

11048번: 이동하기

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
	public static int n, m;
	public static int[][]arr;
    public static void main(String[] args) {
    	Scanner scan = new Scanner(System.in);
    	n = scan.nextInt();
    	m = scan.nextInt();
    	
    	arr = new int[n+1][m+1];
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= m; j++) {
    			arr[i][j] = scan.nextInt();
    		}
    	}
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= m; j++) {
    			arr[i][j] += Math.max(arr[i-1][j], Math.max(arr[i][j-1],arr[i-1][j-1]));
    		}
    	}
    	System.out.println(arr[n][m]);
    }
}

DP의 가장 기본적인 문제라고 생각합니다.

그냥 오른쪽, 왼쪽, 대각선으로 이동할 때 마다 가장 큰 값을 비교하면 된다 생각했지만 그 이상의 행과 열에서 더 큰 값이 나올 수 있으므로 다른 방법으로 풀어야 합니다.

그래서 배열의 왼쪽과 위에 0으로 패딩을 합니다.(0으로 테두리를 만든다는 맥락)

그리고 나서 arr[i][j]의 값은 같은 행 왼쪽 열과 위쪽 행 같은 열, 왼쪽 행 왼쪽 열 중에서 가장 큰 값을 arr[i][j]에 더합니다. 그렇게 되면 차근 차근 모든 행과 열에 대해 더해진 값이 배열을 채우는 새로운 배열이 완성됩니다.

이 때는 DP를 이용하여 덧셈을 진행해주셔도 되고 그대로 arr를 사용하셔도 됩니다. 

표를 이용하여 다시 설명드리자면

0	0	0	0
0	1	2	4
0	2	3	5

라는 배열이 있다고 생각해봅시다. 제일 왼쪽과 위에는 0으로 패딩한 결과입니다. 이 때 arr[2][4]가 가장 최대가 되려면

0	0	0	0
0	1	1 + 2 = 3	3 + 4 = 7
0	1 + 2 = 3	3 + 3 = 6	7 + 5 = 12

가 되어 결론적으로 12가 최대가 됩니다.

즉 모든 배열을 왼쪽, 위쪽, 왼위쪽의 값들을 각각 더한 것 중 최대값을 출력한다고 보면 되겠습니다. 

처음엔 백트래킹으로 풀려고 하다가 시간 초과도 나고 넘 코드가 복잡해져서 DP문제답게 DP개념으로 풀었습니다.