[백준] 2156번 포도주 시식 _ JAVA ( 주석 설명 )

풀이

- '2579번 계단오르기' 문제와 비슷하다.

계단 오르기와 마찬가지로 연속 3잔을 마실 수는 없다.
하지만 마지막 계단(잔)을 밟지 않아도 된다.
따라서 solve(N-2) + ary[N] vs solve(N-3) + ary(N-1) + ary[N] 비교에 이어
마지막 계단(잔)을 밟지 않는 경우인 dp[N-1] == solve(N-1) 과의 비교도 필요하다.

 

1번

→ Top-down 방식

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


public class Main {
    static int[] ary; //포두주 잔에 담긴 포도주의 양을 담는 배열이다.
    
    //포도주의 양이 0 값이 나올 수 있으므로, 빈 공간을 체크하기 위해 Integer을 사용했다.
    //N번째 포도주 잔을 선택했을 때 포도주를 최대로 마실 수 있는 양을 담는 배열이다.
    static Integer[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ary = new int[N+1]; //인덱스는 1부터 시작할 예정이다.
        dp = new Integer[N+1];

        for(int i=1;i<=N;++i){
            ary[i] = Integer.parseInt(br.readLine());
        }

        ary[0] = 0; //0번째 잔의 포도주 양은 0이다.
        dp[0] = 0;
        dp[1] = ary[1]; //1번째 잔을 선택했을 때 최대로 마실 수 있는 양은 1번째 양 그 자체이다.

        if(N>=2)
            dp[2] = ary[1]+ary[2]; //N이 2보다 클 시 dp[2] 배열을 정의해준다.

        System.out.println(solve(N)); //N번째 포도주 잔을 선택했을 때 최대로 마실 수 있는 포도주 양을 출력한다.
    }

    //계단 오르기와 마찬가지로 연속 3잔을 마실 수는 없다.
    //하지만 마지막 계단(잔)을 밟지 않아도 된다.
    //따라서 solve(N-2) + ary[N] vs solve(N-3) + ary(N-1) + ary[N] 비교에 이어
    //마지막 계단(잔)을 밟지 않는 경우인 dp[N-1] == solve(N-1) 과의 비교도 필요하다.
    
    //Top-down 방식
    private static Integer solve(int N) {
        if(dp[N]==null){ //null 값일 시 계산을 실시하고, 값이 존재할 시 바로 return을 해준다.
            dp[N] = Math.max(Math.max(solve(N-2), solve(N-3)+ary[N-1])+ary[N], solve(N-1));
        }
        return dp[N];
    }
}

 

---

 

2번

→ Bottom-up 방식

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


public class Main {
    static int[] ary; //포두주 잔에 담긴 포도주의 양을 담는 배열이다.

    //포도주의 양이 0 값이 나올 수 있으므로, 빈 공간을 체크하기 위해 Integer을 사용했다.
    //N번째 포도주 잔을 선택했을 때 포도주를 최대로 마실 수 있는 양을 담는 배열이다.
    static Integer[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ary = new int[N+1]; //인덱스는 1부터 시작할 예정이다.
        dp = new Integer[N+1];

        for(int i=1;i<=N;++i){
            ary[i] = Integer.parseInt(br.readLine());
        }

        ary[0] = 0; //0번째 잔의 포도주 양은 0이다.
        dp[0] = 0;
        dp[1] = ary[1]; //1번째 잔을 선택했을 때 최대로 마실 수 있는 양은 1번째 양 그 자체이다.

        if(N>=2)
            dp[2] = ary[1]+ary[2]; //N이 2보다 클 시 dp[2] 배열을 정의해준다.

        System.out.println(solve2(N)); //N번째 포도주 잔을 선택했을 때 최대로 마실 수 있는 포도주 양을 출력한다.
    }

    //계단 오르기와 마찬가지로 연속 3잔을 마실 수는 없다.
    //하지만 마지막 계단(잔)을 밟지 않아도 된다.
    //따라서 solve(N-2) + ary[N] vs solve(N-3) + ary(N-1) + ary[N] 비교에 이어
    //마지막 계단(잔)을 밟지 않는 경우인 dp[N-1] == solve(N-1) 과의 비교도 필요하다.

    //Bottom-up 방식
    private static Integer solve2(int N){
        for(int i=3;i<=N;++i){
            dp[i] = Math.max(Math.max(dp[i-2], dp[i-3]+ary[i-1])+ary[i], dp[i-1]);
        }

        return dp[N];
    }
}