[ DP ] 11048번 이동하기

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

11048번: 이동하기

 

---

 

문제

 

---

해결 방법

처음 문제를 접했을 때, 단순한 완전탐색 문제라고 생각했습니다.

사탕의 최댓값을 구하기 위해 모든 칸을 탐색하여 진행하는 방식을 떠올렸습니다.

마침 이동하는 범위도 (0,1) (1,0) (1,1) 이기에 범위도 신경쓸 부분이 줄어들었다 생각했습니다.

 

처음 작성한 코드는 아래와 같습니다.

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

public class Main {
    static int[] mx = {1, 0, 1};
    static int[] my = {0, 1, 1};
    static int[][] maze;
    static int N, M;
    static int answer = 0;

    static void DFS(int x, int y, int candy) {
        if(x == N-1 && y == M-1) {
            answer = Integer.max(answer, candy);
            return;
        }

        int len = mx.length;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                int nx = x + mx[i];
                int ny = y + my[i];

                if(nx<N && ny<M) {
                    DFS(nx, ny, candy+maze[nx][ny]);
                }
            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        maze = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                maze[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        DFS(0, 0, maze[0][0]);

        System.out.println(answer);

    }
}

 

이렇게 풀고 나니 시간 초과가 발생하였습니다.

문제를 다시 읽어보니 가로 세로의 범위가 1,000이었고 시간 제한인 1초를 넘어가게 됩니다.

 

이후 문제를 접근할 방법을 Dynamic Programming으로 변경하였습니다.

핵심 원리는 이전에 계산한 내용을 메모리에 저장해 불필요한 연산을 줄이는 것 입니다.

 

---

코드

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        maze = new int[N+1][M+1];
        dp = new int[N+1][M+1];

        for (int i = 1; i < N+1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < M+1; j++) {
                maze[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < M + 1; j++) {
                dp[i][j] = Integer.max(dp[i - 1][j] + maze[i][j], dp[i][j - 1] + maze[i][j]);
            }
        }

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

    }
}

dp 배열에 현재 위치의 사탕 개수와 이전 칸에 있는 사탕의 개수를 합쳐 넣어줍니다.

 

움직이는 칸이 (0,1) (1,0) (1,1)입니다.

dp[i-1][j] + maze[i][j]는 1,0을 움직이는 연산이고, 

dp[i][j-1] + maze[i][j]는 0,1을 움직이는 연산입니다.

 

1,1을 움직이는 연산을 추가하지 않은 이유는 현재 문제가 사탕 개수의 최댓값을 구하는 문제이기 때문입니다.

최대한 많은 칸을 움직여야 합니다. 1,1을 움직인다면 다른 두 연산에 비해 한 칸을 거르게 되기에 추가하지 않았습니다.