[자바] 백준 11909 - 배열 탈출 (java)

목차

문제 : boj11909

 

 

필요 알고리즘

• DP (동적 계획법)
  
  • DP를 알고 있다면 쉽게 해결 가능한 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  need(X, Y)를 X 좌표에서 Y 좌표로 갈 때 필요한 비용이라고 하자. 예를들어 X가 (1,1), Y가 (1,2) 이고, 배열의 값이 각각 3과 5였다면 need(X, Y)는 3이다.

 

  이 때 dp[a][b]는 (a, b) 좌표로 가는데 필요한 최소 비용이라고 하자. 그렇다면 점화식은 다음과 같다.

dp[a][b] = min( dp[a-1][b] + need((a-1, b), (a,b)), dp[a][b-1] + need((a, b-1), (a,b)))

 

  말로 설명해보면 "(a, b)의 최소 비용은 (a-1, b)까지의 최소비용에 (a-1, b)에서 (a,b)로 가는 비용을 더한 값과, (a, b-1)까지의 최소비용에 (a, b-1)에서 (a,b)로 가는 비용을 더한 값 중 작은 값이다."

 

  점화식이 나왔으니 그대로 코드로 옮겨주면 된다.

 

코드 : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n+1][n+1];
        for (int[] row : arr) Arrays.fill(row, -1100000000);
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] dp = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 && j == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = dp[i][j-1] + need(arr, new int[]{i, j-1}, new int[]{i, j});
                dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + need(arr, new int[]{i-1, j}, new int[]{i, j}));
            }
        }

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

    private int need(int[][] arr, int[] from, int[] to) {
        int f = arr[from[0]][from[1]];
        int t = arr[to[0]][to[1]];

        if (f > t) return 0;
        return t-f+1;
    }
}