[백준][Java][DP] - G5_2096_내려가기

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

2096번: 내려가기

🌿 - 문제 설명

📌- 풀이

 

여러가지 방법들을 생각해봤다. 처음부터 아래까지 전부 완전 탐색을 하면 어떨까?

 

이런식으로 계속해서 완전탐색을 하게 된다면 결과값이 나오게 될 것이다.

하지만 여기서 문제점이

N이 최대 10만까지 이므로 숫자가 늘어날수록 연산해야 할 양이 기하급수적으로 늘어나기 때문에 분명 시간초과가 날 것으로 예상된다.

 

여기서 다른 방법으로 DP를 생각했다.

 

DP(다이나믹 프로그래밍)이란?

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

 

여기에 자세하게 나와있지만 짧게 요약하자면 

하나의 큰 문제를 여러개의 작은 문제로 나누어서 결과를 저장하고 그 결과들로 다시 큰 문제를 만드는 것.

 

이 문제에서

 

arr[i][j] 값을 구하기 위해서 이전 값들의 최소값과 최댓값이 필요하기 때문에

min값과 max값들을 각각의 배열에 저장해주면서 현재 값을 업데이트 시켜주면 된다고 생각했다.

 

 

 

arr[i][j] 의 최소값과 최대값은

 

j가 0일 때는 arr[i][-1]의 값이 없기 때문에 j, j+1 

maxDp[i][j] = Math.max(maxDp[i-1][j],maxDp[i-1][j+1]) + arr[i][j];
minDp[i][j] = Math.min(minDp[i-1][j],minDp[i-1][j+1]) + arr[i][j];

 

j가 1일 때는 전부 다 비교를 해줘야 하기 때문에

maxDp[i][j] = Math.max(Math.max(maxDp[i-1][j],maxDp[i-1][j+1]),maxDp[i-1][j-1]) + arr[i][j];
minDp[i][j] = Math.min(Math.min(minDp[i-1][j],minDp[i-1][j+1]),minDp[i-1][j-1]) + arr[i][j];

 

j가 2일 때는

maxDp[i][j] = Math.max(maxDp[i-1][j],maxDp[i-1][j-1]) + arr[i][j];
minDp[i][j] = Math.min(minDp[i-1][j],minDp[i-1][j-1]) + arr[i][j];

 

이런식으로 DP 배열을 쌓아갔고, 마지막까지 결과를 계산하고 나온 최대값과 최소값을 출력해주는 것으로 마무리 했다.

 

int n = Math.max(Math.max(maxDp[N - 1][0], maxDp[N - 1][1]), maxDp[N - 1][2]);
int m = Math.min(Math.min(minDp[N - 1][0], minDp[N - 1][1]), minDp[N - 1][2]);

System.out.println(n + " " +m);

DP 문제 치고 어려운 편은 아니었지만 빠르게 점화식을 세워서 한번만에 정확하게 푼 문제여서 한번 정리를 해보고 싶었다.

 

다른 DP문제들도 더 잘 풀 수 있도록 많이 풀어보자

🔥 - Java 전체 코드

 

package DP.G5_2096_내려가기;

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

public class Main {
        public static int N,M;

        static int[][] arr;
        static int[][] maxDp, minDp;


    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());

        arr = new int[N][3];
        maxDp = new int[N][3];
        minDp = new int[N][3];

        for(int[] list : minDp){
            Arrays.fill(list,Integer.MAX_VALUE);
        }


        for(int i =0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<3;j++){
                int num = Integer.parseInt(st.nextToken());
                if (i == 0) {
                    minDp[i][j] = num;
                    maxDp[i][j] = num;
                }
                arr[i][j] = num;
            }
        }

        for(int i =1;i<N;i++){
           for(int j =0; j<3;j++){
               if(j ==0){
                   maxDp[i][j] = Math.max(maxDp[i-1][j],maxDp[i-1][j+1]) + arr[i][j];
                   minDp[i][j] = Math.min(minDp[i-1][j],minDp[i-1][j+1]) + arr[i][j];
               }else if( j == 1){
                   maxDp[i][j] =Math.max(Math.max(maxDp[i-1][j],maxDp[i-1][j+1]),maxDp[i-1][j-1]) + arr[i][j];
                   minDp[i][j] =Math.min(Math.min(minDp[i-1][j],minDp[i-1][j+1]),minDp[i-1][j-1]) + arr[i][j];
               }else{
                   maxDp[i][j] = Math.max(maxDp[i-1][j],maxDp[i-1][j-1]) + arr[i][j];
                   minDp[i][j] = Math.min(minDp[i-1][j],minDp[i-1][j-1]) + arr[i][j];
               }


           }
        }


        int n = Math.max(Math.max(maxDp[N - 1][0], maxDp[N - 1][1]), maxDp[N - 1][2]);
        int m = Math.min(Math.min(minDp[N - 1][0], minDp[N - 1][1]), minDp[N - 1][2]);

        System.out.println(n + " " +m);



    }

}