[BOJ11048] 이동하기

문제 링크

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

풀이

0. 문제 해석

N x M 크기의 미로가 주어지고, 각 칸에는 특정 개수의 사탕이 놓여 있다. (1, 1)에서 출발하여 (N, M)까지 이동하면서 얻을 수 있는 사탕의 최대 개수를 찾는 문제이다. 이동은 오른쪽, 아래쪽, 그리고 대각선 아래 오른쪽 세 방향으로만 가능하다.

1. 접근 방법

특정 위치 (i, j)까지 모을 수 있는 사탕의 최대 개수는 그 이전 위치들까지 모은 사탕의 최대 개수에 의해 결정된다. 즉, 부분 문제의 최적 해결책이 전체 문제의 최적 해결책으로 이어지는 구조를 가지고 있다. 이러한 특성은 다이나믹 프로그래밍(DP)을 적용하기에 매우 적합하다.

DP 테이블 dp[i][j]를 (1, 1)에서 (i, j)까지 도달했을 때 얻을 수 있는 사탕의 최대 개수로 정의하고 문제를 해결한다.

2. 아이디어

(i, j) 위치로 도달하기 위한 직전 단계는 다음 세 가지 경우 중 하나이다.

1. 위쪽 칸 (i-1, j)에서 아래로 이동
2. 왼쪽 칸 (i, j-1)에서 오른쪽으로 이동
3. 왼쪽 위 대각선 칸 (i-1, j-1)에서 대각선으로 이동

따라서 (i, j)까지의 최대 사탕 개수는, 위 세 위치까지의 최대 사탕 개수 중 가장 큰 값에 현재 위치 (i, j)의 사탕 개수를 더한 것과 같다. 이를 점화식으로 표현하면 다음과 같다.

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

여기서 map[i][j]는 (i, j)에 놓인 사탕의 개수이다. 이 점화식을 이용하여 DP 테이블을 (1, 1)부터 (N, M)까지 순차적으로 채워나가면, 최종적으로 dp[N][M]에서 해답을 찾을 수 있다.

3. 동작 방식

1. 미로의 크기 N, M과 각 칸의 사탕 정보를 담을 map 배열을 입력받는다.
2. 최대 사탕 개수를 저장할 dp 배열을 N+1, M+1 크기로 생성한다.
3. 이중 for문을 사용하여 i는 1부터 N까지, j는 1부터 M까지 순회한다.
4. 각 순회에서 dp[i][j] 값을 점화식에 따라 계산한다. 이전 위치인 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 중 최대값을 찾아 현재 위치의 사탕 수 map[i][j]를 더한다.
5. 모든 순회가 끝나면 dp[N][M]에 (N, M)까지 도달했을 때의 최대 사탕 개수가 저장된다.
6. dp[N][M] 값을 출력한다.

4. 코드

package BOJ11048;

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

public class Main {
    static int[][] dp;
    static int[][] map;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader([System.in](http://System.in)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N + 1][M + 1];
        dp = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //상향식(Bottom-Up)
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {

                int prevMax = Math.max(dp[i - 1][j], dp[i][j - 1]);
                prevMax = Math.max(prevMax, dp[i - 1][j - 1]);

                dp[i][j] = map[i][j] + prevMax;
            }
        }

        System.out.println(dp[N][M]);
    }
}