문제 이해

포도주를 마시려고 하는데, 3잔 연속으로 마실 수는 없다.
총 n개의 포도주 잔이 있고, 각 포도주 잔에는 정해진 수치만큼의 포도주가 들어 있다.

이 때, 포도주를 가장 많이 마실 수 있는 경우를 구하는 문제이다.

---

문제 풀이

내가 포도주를 마실 수 없는 경우는 딱 1가지이다.

2칸 전의 포도주와 1칸 전의 포도주를 모두 마신 경우

따라서 내가 지금 먹고 있는 포도잔이 몇번 연속으로 마시는 포도주인지 기록할 필요가 있다.

따라서 배열을 N*3만큼 준비한다.
arr[K][i]는 K번째 음료수를 마시는데, K번째 음료수는 연속으로 i번째 마시는 상황인 것이다.
즉, arr[K][0]은 K 포도주를 안 마신 상황, arr[K][1]은 K 포도주를 마시고 K-1 포도주는 마시지 않은 상황, arr[K][2]는 K, K-1 포도주를 마신 상황이다.
K,K-1,K-2 포도주를 마시는 순간 문제 조건에 위반하므로 고려할 필요가 없다.

arr[K][0]은 K 포도주를 안 마실 것이므로 K-1번째를 마시는 상황 중 가장 큰 값을 그대로 가지고 오면 될 것이다.
arr[K][1]은 K 포도주를 마시고 K-1포도주는 마시면 안 되기 때문에 arr[K-1][0] 값을 가지고 오고, K 포도주는 마실 것이므로 cost[K]를 더해준다.
arr[K][2]는 K-1포도주를 마신 상황이므로 arr[K-1][1] 값에 cost[K]를 더해줘야 한다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[] cost;
	static long[][] DP;
	
	static void dp() {
		for(int i =1;i<N+1;i++) {
            // 문제 풀이에서 설명했던 점화식
			DP[i][0] = Math.max(Math.max(DP[i-1][0],DP[i-1][1]),
                                                          DP[i-1][2]);
			DP[i][1] = DP[i-1][0] + cost[i];
			DP[i][2] = DP[i-1][1] + cost[i];
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		cost = new int[N+1];
		DP = new long[N+1][3];
		//DP[i][0] : i번째를 안마심
		//DP[i][1] : i번째를 첫번째로 마셨음
		//DP[i][2] : i번째를 두번째로 마셨음
		
		for(int i =1;i<N+1;i++) {
			cost[i] = sc.nextInt();
		}
		
		dp();
		
		System.out.println(Math.max(Math.max(DP[N][0],DP[N][1]),
                                                          DP[N][2]));
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2,3번째 줄 틀렸습니다 : DP[i][0]의 경우 i-1번째를 안 마시고 i번째도 안 마시는 상황이 최대가 될 수도 있다. 즉, max(DP[i-1][0], DP[i-1][1], DP[i-1][2])가 되어야 한다. 그런데 i-1번째와 i번째를 둘 다 안 마시는 경우는 답에 포함되지 않을 것이라 지레 짐작하여 코드를 생략해서 틀렸다.