[BOJ] 11048.이동하기(DP).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

 

최대 N, M 을 간과하고 푼다면

완탐으로 풀릴것이라고 착각하고 시간초과가 나버린다.

내가 그랬다.. 하하핳

최악의 경우에는 1000^4 까지 나올 수 있다.

1000x1000 map에서 각 칸으로부터 최대 사탕 개수를 찾기 위해 1000x1000 을 다 돌아봐야할 수 있다.

결국 DP로 해결해야만 한다..

문제가 짧다고 시간복잡도를 간과하지말길..

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ11048 {       static int R, C, map[][], dp[][];       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());           R = Integer.parseInt(st.nextToken());         C = Integer.parseInt(st.nextToken());         map = new int[R+1][C+1];         dp = new int[R+1][C+1];           // 미로 정보 입력         for (int i = 1; i <= R; i++) {             st = new StringTokenizer(br.readLine());             for (int j = 1; j <= C; j++) {                 map[i][j] = Integer.parseInt(st.nextToken());             }         }                  // [r-1][c-1], [r-1][c], [r][c-1] 까지의 사탕 개수 + 현재 위치에 있는 사탕 개수         for (int r = 1; r <= R; r++) {             for (int c = 1; c <= C; c++) {                 dp[r][c] = Math.max(dp[r-1][c-1] + map[r][c],                          Math.max(dp[r-1][c] + map[r][c], dp[r][c-1] + map[r][c]));             }         }                  System.out.println(dp[R][C]);     }   }   Colored by Color Scripter

cs

#. Code_v2

문제를 다시 보면

사탕의 개수를 저장하는 map을 관리할 필요가 없다.

테두리가 0인 dp 배열에

각 좌표에 해당하는 사탕 개수를 입력받으면서

dp[r-1][c], dp[r][c-1] 의 최댓값에 더해주면 된다.

dp 배열에 바로바로 사탕 개수를 갱신해주는 것이다.

dp[r-1][c-1] 를 확인해주지 않는 이유는

dp[r-1][c], dp[r][c-1] 만 체크해줘도 어차피 자연스럽게 dp[r-1][c-1] 가 체크된다.

첫 번째 코드보다 훨씬 간결해졌다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ11048_v2 {
 
    static int R, C, dp[][];
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        dp = new int[R+1][C+1];
        
        for (int i = 1; i <= R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= C; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + Integer.parseInt(st.nextToken());
            }
        }
        
        System.out.println(dp[R][C]);
    }
 
}