[백준] 2156 포도주 시식

문제 출처: www.acmicpc.net/problem/2156

2156번: 포도주 시식

: 포도주를 최대한 많이 마실 수 있도록 하여 마신 포도주 양을 구해야 한다.

: 포도주를 마실 때 2가지 규칙이 있다.

- 포도주 잔을 선택하면 그 잔에 있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

- 연속으로 놓여있는 3잔을 모두 마실 수는 없다.

: 따라서 경우를 3가지로 나누어 볼 수 있다.

: 이전에 마신경우, 이전에 마시지 않은 경우, 현재 마시지 않을 경우로 나눠서 생각해 볼 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		int[][] D = new int[N+1][3];
		int[] v = new int[N+1];
		for(int i = 1; i < N+1; i++) {
			v[i] = Integer.parseInt(br.readLine());
		}
//		System.out.println(Arrays.toString(v));
		D[1][0] = v[1];
		D[1][1] = v[1];
		// 0이 이전꺼 마신경우, 1이 안마신 경우
		for(int i = 2; i < N+1; i++) {
			D[i][0] = D[i-1][1] + v[i];
			D[i][1] = Math.max(D[i-2][0], Math.max(D[i-2][1], D[i-1][2])) + v[i];
			D[i][2] = Math.max(D[i-1][0], Math.max(D[i-1][1], D[i-1][2]));
		}
//		for(int[] sub : D)
//			System.out.println(Arrays.toString(sub));
		int a = Math.max(D[N-1][0], D[N-1][1]);
		int b = Math.max(D[N][1], D[N][0]);
		System.out.println(Math.max(a, b));
	}
}