[JAVA]백준_11909_배열탈출

문제링크

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

11909번: 배열 탈출

 

 

 

package BOJ;

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

public class Main_11909 {
    static int N;
    static int arr[][]; //입력받을 배열
    static int dp[][]; //최소값 저장할 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        dp = new int[N+1][N+1];

        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1;j<=N;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = Integer.MAX_VALUE; //최소값 구하는 배열에 최대값으로 채워주기
            }
        }

        dp[1][1] = 0; //시작점은 1

        //무조건 우측 하니면 아래로 이동
        //막히면 우측으로만 가거나 아래로만 이동
        //상수가 A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]
        //상수는 자신이 위치해 있는 원소의 버튼을 누를 수 있음
        //버튼 누를 시 +1
        //버튼 한 번 누를 시 비용 1원

        int diff = 0; // 이동하는 배열 사이 값 차이

        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(i == N && j == N) break; //도착지 도착 시 탈출
                if(i != N){
                    if(arr[i+1][j] >= arr[i][j]){ ///이동 못할 시
                        diff = arr[i+1][j] - arr[i][j]+1; //버튼 눌러서 값 올려주기
                        dp[i+1][j] = Math.min(dp[i+1][j],diff+dp[i][j]);
                    }
                    else{
                        dp[i+1][j] = Math.min(dp[i+1][j],dp[i][j]);
                    }
                }
                if(j != N){
                    if(arr[i][j+1] >= arr[i][j]){ ///이동 못할 시
                        diff = arr[i][j+1] - arr[i][j]+1; //버튼 눌러서 값 올려주기
                        dp[i][j+1] = Math.min(dp[i][j+1],diff+dp[i][j]);
                    }
                    else{
                        dp[i][j+1] = Math.min(dp[i][j+1],dp[i][j]);
                    }
                }
            }
        }

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