백준 - 2156번 - 포도주 시식

2156번

import java.io.*;
import java.util.*;

public class Main {

	static Integer dp[];
	static Integer wine[];

	static int recur(int N) {
		if (dp[N] == null) {
			if (N == 3) {
				dp[N] = Math.max(Math.max(wine[N-2], wine[N-1]) + wine[N], wine[N-2] + wine[N-1]);
			}

			else if (N > 3) {
				dp[N] = Math.max(Math.max((recur(N-3) + wine[N-1] + wine[N]), (recur(N-2) + wine[N])), recur(N-1));
			}
		}
		return dp[N];
	}
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(bf.readLine());
		dp = new Integer[num+1];
		wine = new Integer[num+1];
		for (int i = 1; i<num+1; i++) {
			wine[i] = Integer.parseInt(bf.readLine());
		}
		dp[0] = 0;
		dp[1] = wine[1];

		// num이 1로 주어졌을때 ArrayIndexOutOfBounds나는것을 대비
		if (num > 1) {
			dp[2] = wine[1] + wine[2];
		}

		System.out.println(recur(num));

	}

}

풀이

점화식 찾기가 너무 힘들다...
포인트는 마지막인덱스를 안더한값이 더 클 수 있다는 점이다.

• N-3까지 총합 최댓값 + N-2번째 숫자 + N번째 숫자
• N-2까지 총합 최댓값 + N번째 숫자
• N-1까지 총합 최댓값

위의 세가지 중에 제일 큰수가 정답이다.