[알고리즘 - 백준] 2156번 포도주 시식(java)

백준 포도주 시식 문제 링크

3잔은 연속해서 마시시 않아야한다는 조건이 있다. 이 경우 현재 인덱스를 기준으로 oox, oxo, xoo와 같이 마셨는지 안마셨는지 3가지 상황에서 dp[i]값을 갱신하여 마신 최댓값을 구할 수 있다.

예로, 현재 인덱스가 2일 때를 생각해보자.
1. oox인 경우

i=0, i=1 :: 마셨고, i=2 :: 마시지 않은 경우다. 이 경우엔 dp[i] = dp[i-1]이 된다.

2. oxo인 경우

i=0, i=2 :: 마셨고, i=1 :: 마시지 않은 경우다. 이 경우엔 dp[i] = dp[i-2]+arr[i]가 된다.

3. xoo인 경우

i=1, i-2 :: 마셨고, i=0 :: 마시지 않은 경우다. 이 경우엔 dp[i] = dp[i-3]+arr[i-1]+arr[i]가 된다.

dp[0] = arr[0]이 될 것이고, dp[1] = dp[0]+arr[1]로 초기화하고 i=2부터 n-1까지 반복하며 dp[i]값을 갱신시키면 최댓값을 알 수 있다.

import java.util.*;
import java.io.*;
class Solution{
	static int arr[];
	static long dp[];
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		arr = new int [n];
		
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		dp = new long[n];
		
		dp[0] = arr[0];
		dp[1] = arr[0]+arr[1];
		
		long maxSum = 0;
		for(int i=2;i<n;i++) {
			//1.xoo
			if(i-3>=0)
				dp[i] = Math.max(dp[i], dp[i-3]+arr[i-1]+arr[i]);
			
			//2.oxo
			dp[i] = Math.max(dp[i], dp[i-2]+arr[i]);
			
			//3.oox
			dp[i] = Math.max(dp[i], dp[i-1]);
			
			maxSum = Math.max(maxSum, dp[i]);
		}
		System.out.println(maxSum);
		
	}
}