[BOJ] 11048 - 이동하기

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/11048

11048번: 이동하기

난이도: 실버 1

사용언어: JAVA

 

NxM의 방이 존재하고, 방의 각 칸에는 사탕이 여러 개씩 떨어져 있습니다. 그리고 각 칸에 도착하면 떨어져 있는 사탕들을 모두 주울 수 있습니다.

 

현재 준규는 가장 좌측 상단에 위치하고, 만일 (i, j)라는 위치에 존재한다면, (i+1, j), (i, j+1), (i+1, j+1) 이렇게 세 가지 경우의 수로만 움직일 수 있습니다. 가장 우측 하단에 도착할 때까지 주울 수 있는 사탕의 최대 개수를 구하는 것이 문제입니다.

 

풀이

이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. dp [][]라는 다이나믹 프로그래밍을 위한 배열을 하나 만들어 해당 칸에 도착했을 때까지 주울 수 있는 사탕의 최대 개수를 한 칸 한 칸씩 구해가며 가장 우측 하단까지 도착하면, 마지막에 주울 수 있는 사탕의 최대 개수를 구할 수 있습니다.

 

즉 (i, j)라는 칸에 도착할 때까지 주울 수 있는 사탕의 최대 값은 (i+1, j)까지 주울 수 있는 사탕의 최댓값에, (i, j)에 떨어져 있는 사탕의 수를 더한 값(1)과, (i, j+1)까지 주울 수 있는 사탕의 최댓값에, (i, j)에 떨어져 있는 사탕의 수를 더한 값(2), 마지막으로 (i+1, j+1)까지 주울 수 있는 사탕의 최댓값에, (i, j)에 떨어져 있는 사탕의 수를 더한 값(3), 이 (1), (2), (3) 중에 가장 큰 값을 더한 값이 됩니다.

 

import java.io.*;
import java.util.StringTokenizer;
 
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, M;
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        int[][] arr = new int[N][M]; // 입력값을 담는 배열
        int[][] dp = new int[N][M]; // Dynamic Programming을 위한 배열
        int i, j;
        for (i = 0; i < N; i++) {
            s = br.readLine();
            st = new StringTokenizer(s);
            for (j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        dp[0][0] = arr[0][0];
        for(i=1;i<M;i++)
            dp[0][i] = dp[0][i-1] + arr[0][i]; // dp의 첫 행은 arr 값에 바로 왼쪽 칸의 dp를 더해서 구할 수 있다.
        for(i=1;i<N;i++)
            dp[i][0] = dp[i-1][0] + arr[i][0]; // dp의 첫 열은 arr 값에 바로 위쪽 칸의 dp를 더해서 구할 수 있다.
       // 배열에 크기를 벗어나는 인덱스를 없애기 위해 첫 열과 첫 행을 먼저 채워주었다
        for(i=1;i<N;i++){
            for(j=1;j<M;j++){
                dp[i][j] = Math.max(Math.max(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + arr[i][j];
           } // 위의 설명에서처럼 (1), (2), (3)중 가장 큰 값에 arr 값을 더해주면 된다.
        }
        System.out.println(dp[N-1][M-1]);
    }
}