[백준 : 2156] 포도주 시식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {

	static Integer dp[];
	static int arr[];
	
	public static void main(String[] args) throws Exception, IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		dp = new Integer[N + 1];
		arr = new int[N + 1];
		
		for(int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		dp[0] = arr[0];
		dp[1] = arr[1];
		
		if(N >= 2) {
			dp[2] = arr[1] + arr[2];//find(2) 하면 find(0), find(-1)을 찾게됨
		}
		System.out.println(find(N));
	}
	static int find(int N) {
		if(dp[N] == null) {
			dp[N] = Math.max(Math.max(find(N-2), find(N-3) + arr[N-1]) + arr[N], find(N-1));
		}
		
		return dp[N];
	}
}

 계단오르기랑 정말 비슷하지만 다른 문제!

3개이상 연속하면 안되는 것 똑같지만, 계단오르기는 마지막 계단을 무조건 밟아야하고, 포도주 문제는 마지막 잔을 무조건 마셔야 되는 조건 없음!

마지막의 앞잔에서 마시는것까지가 최대값일 수 있으니까, dp[N]을 넣을때, find(N-1) 이랑 find(N)이랑 비교해서 max값을 두번 찾아준다.