포도주 시식

이 문제는 마신 포도주의 최댓값을 구하는 문제입니다.

최댓값 문제가 나온다면 저는 dp를 먼저 떠올립니다.

• 각 포도주는 모두 마셔야 합니다.
• 연속 3잔 이상 마실 수 없습니다.

연속 3잔을 마실 수 없다고 했으므로, 각 잔을 선택할 때 상태의 경우의 수는

1. 해당 잔을 마시지 않는다. (연속성 깨짐)
2. 이전에 마시지 않았고, 현재 잔을 마신다. (연속 1회)
3. 이전에 마셨고, 현재 잔도 마신다. (연속 2회)

위와 같이 3가지의 경우가 있을 것입니다.

// f(n, continuous)은 n번째 잔을 continuous 연속해서 마셨을 때의 최댓값

f(n, 0) = max(f(n-1, 1), f(n-1, 2))
f(n, 1) = f(n-1, 0) + wine(n)
f(n, 2) = f(n-1, 1) + wine(n)

처음에 저는 이를 위와 같이 점화식을 세워서 풀었으나, 실패했습니다.

이유는 f(n, 0)의 점화식 때문이었는데, 연속해서 2회 마시지 않는 경우는 없을 거라고 단순히 생각했었기 때문입니다. 하지만 OOXXOO와 같이, 2회 연속 마시지 않는 경우가 존재합니다.

예를 들어 [200, 200, 10, 10, 200, 200]의 경우, 기존의 점화식 대로라면 문제를 해결할 수 없습니다.

따라서 점화식을 아래와 같이, f(n, 0)을 계산할 때 이전에 마시지 않았을 때를 추가하여 수정해서 풀면 됩니다.

f(n, 0) = max(f(n-1, 0), f(n-1, 1), f(n-1, 2))
f(n, 1) = f(n-1, 0) + wine(n)
f(n, 2) = f(n-1, 1) + wine(n)

코드

package bj.comito.codeplus.basic.week06;

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

public class BJ2156 {
    private static final int NONE = 0;
    private static final int ONCE = 1;
    private static final int TWICE = 2;

    private static int N;
    private static int[] wines;

    public static void main(String[] args) throws Throwable {
        input();

        System.out.println(dp());
    }

    private static void input() throws Throwable {
        final BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in), 1<<15
        );

        N = Integer.parseInt(br.readLine());
        wines = new int[N];

        for (int ni = 0; ni < N; ni++) {
            wines[ni] = Integer.parseInt(br.readLine());
        }

        br.close();
    }

    private static int dp() {
        final int[] none = new int[N];
        final int[] once = new int[N];
        final int[] twice = new int[N];

        none[0] = 0;
        once[0] = wines[0];
        twice[0] = wines[0];

        for (int ni = 1; ni < N; ni++) {
            none[ni] = max(none[ni-1], once[ni-1], twice[ni-1]);
            once[ni] = wines[ni] + none[ni-1];
            twice[ni] = wines[ni] + once[ni-1];
        }

        return max(none[N-1], once[N-1], twice[N-1]);
    }

    private static int max(int... nums) {
        int ret = Integer.MIN_VALUE;

        for (int n: nums) {
            if (n > ret) {
                ret = n;
            }
        }

        return ret;
    }
}