백준 2156 포도주 시식 [JAVA]

문제 해석

• 문제 자체는 크게 이해에 어려운 점은 없다. 간단하게 말하자면 그냥 "포도주를 가장 많이 마시는 루트는 어떻게 되냐(단, 이웃한 3잔을 연속 마실 수 없다.)" 인 것 같다.
• 전에 풀었던 문제도 이러한 비슷한 문제가 있었던 것 같은데 아무튼! 다시 정리하자면,
  1. 포도주잔의 개수(N) 와 각각의 포도주잔에 들어가 있는 포도주의 양을 입력받는다.
  2. 입력을 모두 받았다면, 연속 3잔을 마시지 않는 조건에서 최대 얼마큼 마실 수 있는지 출력한다.

코드

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

public class Main {
    static Integer dp[];

    static int grape[];

    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine()); //입력 개수 (포도잔의 개수)

        //배열 초기화
        grape = new int[N+1];
        dp = new Integer[N+1];

        //값 세팅 (포도주 한 잔의 양)
        for(int i = 1; i <= N; i++){
            grape[i] = Integer.parseInt(br.readLine());
        }

        //메모이제이션을 위해 초기값 지정
        dp[0] = 0;
        dp[1] = grape[1];

        // 만약 입력받은 포도잔의 개수가 1개 이상이면서 2잔인 경우
        // 당연히 첫잔과 두번째 잔을 더한게 최댓값이 된다.
        // (dp[2] = grape[1] + grape[2]) 일 수 밖에 없는
        if(N > 1){
            dp[2] = grape[1] + grape[2];
        }

        System.out.println(Top_Down(N));
    }

    static int Top_Down(int depth){
        if(dp[depth] == null){ //한번도 조회하지 않았다면
            //일단, N-2(전전)번째의 누적합과 N-3(전전전)번째의 누적합 + 그냥 전의 포두주 잔의 양 값 중 최댓값을 구한다. (연속 3잔은 마실 수 없기 때문)
            // 구했다면, 그 위의 구한 값에서 지금 잔의 포도잔의 양을 더한 값과 이전 누적합 포도주양 중 최댓값을 구한다.
            dp[depth] = Math.max(Math.max(Top_Down(depth-2), Top_Down(depth-3)+grape[depth-1])+ grape[depth], Top_Down(depth-1));
        }
        return dp[depth];
    }

}

결과

느낀 점

• 확실히 저번에 동적프로그래밍에 대해 정리를 하고 넘어가서인지 전처럼 이해하는데 오래걸리지 않았다. 물론 아직도 부족한 점이 많긴 하지만... 😭