Baekjoon2156: 포도주 시식

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

 

풀이

계단 문제와 유사하다. 3개의 항을 연속해서 선택할 수 없다는 제한조건이 있으며 최대값을 골라내야 한다.

경우의 수를 그림으로 표현해본다. 끝 항 4개를 기준으로 경우의 수를 나눠본다

N-2항	N-1항	N항
X	O	O
O	X	O
X / O	O	X

N항을 선택하는 경우가 있고 아닌 경우가 존재한다.

선택했을 때, 점프를 해야만하는 N-1항과 점프를 하지 않아도 되는 N-2항을 비교해 더 큰 값을 가져온다

 → dp[N][점프 선택 가능] = Math.max( dp[N-1][점프 필수],  dp[N-2][점프 선택 가능]);

선택하지 않았을 때, 점프를 할 수도 있고 안할 수도 있는 N-1항을 가져온다

 → dp[N][선택하지 않음] = dp[N-1][ 점프 선택 가능 ]

 

N=6

100 400 2 1 4 200 을 입력한다 → 위의 논리대로라면 701이 나오지만 실제 답은 704이다.

200과 4를 선택하고 두번을 건너 뛰었기 때문이다. 조건을 하나 더 추가해준다.

선택하지 않았을 때, 한 번 더 건너뛸 수 있도록 한다

 → dp[N][선택하지 않음] = Math.max( dp[N-1][ 점프 선택 가능 ], dp[N-2][ 점프 선택 가능 ] )

import java.util.Scanner;
public class Main {
	static Integer dp[][];
	static int[] wine;
	static Integer drink(int N, int C) {
		if(N<=0)return dp[0][C];
		else if(dp[N][0]==null || dp[N][1]==null || dp[N][2]==null) {
			dp[N][0] = Math.max(drink(N-1, 2),Math.max(drink(N-1,1)+wine[N-1],drink(N-2,0)+wine[N-1]));
			dp[N][1] = Math.max(drink(N-2,0)+wine[N-1], drink(N-2,2)+wine[N-1]);
			dp[N][2] = Math.max(drink(N-1,0), drink(N-2,0));
			
			// 0은 점프 선택가능한 경우: 점프를 한 결과와 하지 않은 결과 중 최대값을 가져온다
			// 1은 점프 필수: 점프를 한 값을 가져온다
			// 2는 선택하지 않음: 반례를 고려해 전전항으로 보낼 수 있도록 한다
		}
		return dp[N][C];
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		wine = new int[n];
		dp = new Integer[n+1][3];
		//0은 붙어있지 않아 점프 선택 가능, 1은 붙어있어 점프필수, 2는 선택되지 않았을 때
		
		for(int i=0;i<n;i++){
			wine[i]=sc.nextInt();
		} //배열에 입력값을 집어넣는다
		int max=0;
		dp[0][0]=0; dp[0][1]=0; dp[0][2]=0;
		for(int i=0; i<3; i++)
		max=Math.max(max, drink(n,i));
		System.out.print(max);
		//셋 중 최대값 출력
	}
}