[백준]2156 포도주 시식

dp랑 좀 친해진다고 생각했는데 두번 연속 배반당하고 풀이의 도움을 받았다.. 이것도 코드는 현타올 정도로 짧은데 이해가 안돼서 계속 보고 또 보고 했다 🥲

package baekjoon;

import java.util.Scanner;

public class Main_2156 {
    public static void main(String[] args) {
        // 잔에 있는 건 다 마셔야하고 마신 후 제자리에 둬야함
        // 연속 3잔을 마실 수 없음
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();                // 포도주 잔의 개수
        int[] amount = new int[n + 1];       // 포도주 양을 저장한 배열
        int[] dp = new int[n+1];

        // 잔이 3개 미만일 경우 모든 잔을 먹어야 최댓값
        for (int i = 1; i <= n; i++) {
            amount[i] = sc.nextInt();
            if(i<3) {
                dp[i] += amount[i] + dp[i-1];
            }
        }

        // O O X 전전 와인을 먹고 현재 와인을 먹는다
        // O X O 전 와인을 먹고 현재 와인을 먹는다
        // X O O 전과 전전 와인을 먹고 현재 와인을 먹지 않는다
        // 세 개의 경우의 수가 있음 (3잔을 연달아 마시면 안되므로)
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2], dp[i-3] + amount[i-1]) + amount[i]);
        }

        System.out.println(dp[n]);

    }
}

풀이 👩‍💻
세잔을 연속으로 마실 수 없으므로 경우의 수가 총 세가지 나온다.
O O X 전전과 전 와인을 마시고 현재 와인을 마시지 않기
O X O 전전 와인과 현재 와인을 마시고 직전 와인을 마시지 않기
X O O 전전 와인을 마시지 않고 직전 와인과 현재 와인을 마시기

일단 두번째 잔까지는 나온 모든 잔을 마신게 최대값이므로 입력과 동시에 배열을 세팅해준다.

세번째잔부터 연속으로 마실 수 없다는 조건이 해당되기 때문에 3부터 for문을 돌려준다.(사실 그냥 여기부터 이해 안됐다 계속 보고 또 보고 풀이 검색하고 또 하고..)

일단 현재 와인을 마셨을 경우의 최댓값을 체크한다.

Math.max(dp[i-2], dp[i-3] + amount[i-1]) + amount[i]

현재 와인을 마시려면 직전 와인을 안먹거나 전전 와인을 안먹거나이다.
O X O 와 X O O 의 최댓값을 먼저 비교한다.
dp[i-2] - 전전 와인을 마셨을 때까지의 최댓값과
dp[i-3] + amount[i-1] 전전 와인을 안마시기 때문에 전전전 와인을 마셨을때까지의 최댓값에 직전와인을 더하고
현재와인을 마신걸 최종적으로 더해준다.

그리고 이 값과 현재 와인을 마시지 않았을 경우를 비교해준다.
dp[i-1] - 직전 와인을 마셨을 때까지의 최댓값

그럼 아주 간단하게 답이 나온다. 풀이를 보고도 코드를 구현하기까지 너무 어려웠다. 다시 생각하고 풀어봐야겠다.😭