백준 11048 - 이동하기

Java

11048 번 - 이동하기

문제

접근 방법

메모리제이션을 위한 dp[][] 배열을 생성하고 Bottom - up 점화식으로 해결한다.

문제의 조건에 의하면 대각선으로 이동하는 것보다, 아래 -> 오른쪽 or 오른쪽 -> 아래일 경우 이득이 더 크므로 대각선을 제외한다.
점화식

dp[i][j] = Math.max(dp[i - 1][j] + map[i][j], dp[i][j - 1] + map[i][j])

점화식을 보았을 때, i - 1 or j - 1 이므로, 첫 행렬의 크기를 n + 1, m + 1로 두어 ArrayOutOfIndex를 피한다

코드

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

public class Main {
	static int n,m,result;
	static int[][] map, dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	map = new int[n + 1][m + 1];		// 0번째 행렬의 빈 공간을 추가한다.
    	dp = new int[n + 1][m + 1];
    	for(int i = 1; i <= n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 1; j <= m; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    	}

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

    	System.out.println(dp[n][m]);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점