문제

코드

import java.util.Scanner;

public class q2156 {
    public static void main(String[] args) {
        // 연속세잔은 못마심
        // 1. 한잔 마시고 ... 연속 두번 : 0 ~ n-3 중 max값 + grape[n-1] + grape[n]
        // 2. 두잔 연속 마시고 ... 한 번 : 0 ~ n-2 중 max값 + grape[n];
        // ... 는 몇번이든 될 수 있음
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[] grape = new int[N];
        for(int i=0; i<grape.length; i++) grape[i] = sc.nextInt();

        int[] memo = new int[N];
        try {
            memo[0] = grape[0];
            memo[1] = Math.max(grape[0] + grape[1], grape[1]);
            memo[2] = Math.max(grape[1] + grape[2], memo[0] + grape[2]);

            for(int i=3; i<N; i++) {
                int max1 = 0;
                int max2 = 0;
                for(int j=0; j<i-1; j++) {
                    if(max1 < memo[j] && j != i-2) max1 = memo[j];
                    if(max2 < memo[j]) max2 = memo[j];
                }
                memo[i] = Math.max(max1 + grape[i-1] + grape[i] , max2 + grape[i]);
            }
        } catch (Exception e) {}

        int max = 0;
        for(int g : memo) {
            if(max < g) max = g;
        }
        System.out.println(max);
    }
}

풀이

이전 2579(계단 오르기) 문제와 유사하다.
단 여기서는 조건이 조금 다르다.

포도주를 먹을 수 있는 방법은 다음과 같다.
1. 한 잔 마시고...연속 두 잔 마시기 + 단 n-2잔은 마실 수 없다(n-1, n잔을 마시기 때문)
2. 연속 두 잔 마시고...한 잔 마시기 + 단 n-1잔은 마실 수 없다(n잔을 마시기 때문)

해당 문제와 2579와의 차이점은 ... 사이에 들어가는 값의 개수이다.
2579에는 무조건 다음 계단을 올라가야 하기 때문에 ... 에 1개의 값만 들어갈 수 있는 반면,
이 문제에서는 ...에 몇 개의 값이 들어가던 상관 없다.

1의 각각 한 잔과 2의 연속 두 잔에는 이전 메모이제이션 값 중 각각 범위 내의 max 값을 넣어주었다.