백준 2156

문제

---

(포도주랑 와인은 같은 단어로 생각해주세요)

dp[N] : N개의 와인이 주어지고 규칙대로 마실 때, 최대로 마실 수 있는 포도주 양

연속된 세 잔의 와인은 마실 수 없고 재귀적으로 생각했을 때,
N 개의 와인이 주어진다면 아래의 경우로 나눌 수 있다.

1) N 번째 와인을 마시지 않는다.

2) N 번째 와인을 마신다.
2 - 1) N - 2번째 와인을 마시고 N - 1번째 와인은 마시지 않는다.
2 - 2) N - 3번째 와인을 마시고 N - 2번째 와인은 마시지 않는다. 그리고 N - 1번째 와인은 마신다.

1)의 경우는 dp[N - 1]과 같을 것이다.

1), 2-1), 2-2) 경우 중 마실 수 있는 최대 포도주 양을 구하면 됨.

---

주의

dp[2]는 와인이 2잔일 때의 경우이므로 당연히 2잔의 와인을 합한 양이 마실 수 있는 최대 와인의 양이다.
(dp[2] = wines[1] + wines[2])

하지만 와인의 양(n)으로 1이 입력될 수 있으므로 분기를 나누지 않으면

인덱스 오류 난다.(wines[2]가 없으니까...)

---

Code

package test;

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

public class P2156 {

	private static int[] wines;
	private static Integer[] dp;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		wines = new int[n + 1];
		dp = new Integer[n + 1];
		
		for(int i = 1; i <= n; i++) {
			wines[i] = Integer.parseInt(br.readLine());
		}
		
		dp[0] = 0;
		dp[1] = wines[1];
		
		if(n > 1) {
			dp[2] = wines[1] + wines[2];
		}
		
		
		System.out.println(drinkWine(n));
	}
	
	private static int drinkWine(int n) {
		if(dp[n] == null) {
			int temp = Math.max(drinkWine(n - 2), drinkWine(n - 3) + wines[n - 1]) + wines[n];
			dp[n] = Math.max(drinkWine(n - 1), temp);
		}
		return dp[n];
	}

}