[Algorithms] 백준 DP 문제모음 (Top-down 유형)

# 포도주 시식 (2156번)

1. Top-down 유형에 익숙해지자...

2. 항상 기본적인 예외 체크를 신경쓰자...!!! (n이 최소,최대 일 때)

import java.util.Scanner;

public class Main {

    static int[] drink;
    static int[] podoJu;

    //drink(n) : n(마지막) 잔을 마셨을 때 최대로 마시는 양
    //case 1 : drink(n) = pick(n-1)+pick(n)+drink(n-3) //n-1
    //case 2 : drink(n) = pick(n)+drink(n-2)          //n-2
    //case 3 : drink(n) = pick(n)+drink(n-3, n-4, ..) //vast jump
    //case 3 never happen dude.....;;;
    //case 4 : drink(n) = pick(n-1)+pick(n)+ drink(n-3,n-4, ...)
    // for case 3, previousMax : max between drink(0) to drink(n-3)
    public static void makeDrink(int size,int previousMax){

        for(int n=3; n<size; n++){
            previousMax = maxUpdate(drink[n-3],previousMax);

            drink[n]= Math.max(
                    pick(n-1)+pick(n)+previousMax,
                    pick(n)+drink[n-2]);
        }//end for
    }


    public static int pick(int n){
        return podoJu[n];
    }

    public static void printArr(int size){
        for(int i=0;i<size;i++){
            System.out.print(drink[i]+" ");
        }
        System.out.println();
    }

    public static void printPodoArr(int size){
        for(int i=0;i<size;i++){
            System.out.printf("%3d ",podoJu[i]);
        }
        System.out.println();
    }

    public static int maxUpdate(int now, int previousMax){
        return Math.max(now,previousMax);
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        podoJu= new int[n+1];
        drink = new int[n+1];
        for(int i=0;i<n;i++){
            podoJu[i] = sc.nextInt();
        }

        int max = 0;

        drink[0]=pick(0);
        max = maxUpdate(drink[0],max);
        if(n>1){
            drink[1]=pick(0)+pick(1);
            if(n>2){
                drink[2]=Math.max(pick(2)+pick(0), pick(2)+pick(1));
            }
        }

        makeDrink(n,max);

//        printPodoArr(n);
//        printArr(n);

        if(n>1){
            System.out.println(Math.max(drink[n-1],drink[n-2]));
        }else{
            System.out.println(drink[n-1]);
        }

        /* examples
        * 6 6 10 13 9 8 1
        * 6 300 400 2 1 4 200
        * 8 300 400 3 1 2 1 4 200
        * */


    }
}



/* 다른사람 로직 (D는 dp 배열, W는 podoJu)
// D[i-2] : n-2 번째 pick 했을때의 최대양
// D[i-3] : n-3 번째 pick 했을때의 최대양 + podoJu[n-1] pick
// D[i]+W[i] : 위의 두가지 케이스중 큰거 + podoJu[n] pick
// D[i-1] : podoJu[n] pick 안했을때의 최대양 (=n-1 번째 pick 했을때의 최대양)
// 즉, D[i] : n번째 pick 했을때 or 안했을때의 최대양...?
for (int i = 3; i <= N; i++) {
            D[i] = max(D[i - 2], D[i - 3] + W[i - 1]);
            D[i] = max(D[i] + W[i], D[i - 1]);
        }

*/

---

# 계단 오르기 (2579번)

1. 쉽다! 헿ㅎㅎㅎ

import java.util.Scanner;

public class Main{

    //1. 연속3개 ㄴㄴ
    //2. jump는 1~2
    //3. last one should be stepped on ==> Top-down
    // max point calculate

    //0< stair's point <=10000
    //0< num of stairs <=300

    public static int[] stairs;
    public static int[] dp;

    //dp[n] : n번째 계단을 밟았을때 포인트 총합 최대값
    //case1 : stairs[n-1]+dp[n-3]
    //case2 : stairs[n-2]+stairs[n-3]+dp[n-5] (n-4는 밟으면안됨...)
    //case3 : stairs[n-2]+dp[n-4]
    //case2 & case 3 : dp[n-2]
    public static void gameStart(int size){
        for(int n=3;n<=size;n++){
            dp[n]= Math.max(
                    dp[n-3]+stairs[n-1],dp[n-2])
                    + stairs[n];
        }
    }


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        stairs= new int[n+1];
        dp= new int[n+1];
        for(int i=1; i<=n; i++){
            stairs[i]=sc.nextInt();
        }

        //Minimum Exception handling
        if(n<3){
            dp[1]=stairs[1];
            if(n==2){
                dp[2]=stairs[1]+stairs[2];
            }
            System.out.println(dp[n]);
        }
        //Main logic
        else{
            dp[1]=stairs[1];
            dp[2]=stairs[1]+stairs[2];
            gameStart(n);
            System.out.println(dp[n]);
        }
    }

}