[백준 알고리즘] 2156번 포도주 시식 (DP, 자바)

 

 

 

package jae.pro.backjoon;
 
import java.util.Scanner;
 
public class Grape {
 
    static int count;
    static int[] drink;
    static int[] dp;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        count = sc.nextInt();
        drink = new int[count + 1];
        dp = new int[count + 1];
 
        for (int i = 1; i < count + 1; i++) {
            drink[i] = sc.nextInt();
        }
        dp[1] = drink[1];
 
        if (count >= 2)
            dp[2] = drink[2] + dp[1];
        
        for (int i = 3; i < count + 1; i++) {
            // 마지막 포도주를 고를 때를 기준으로  n-1잔을 마실때와 안마실 때 2가지 경우의 수 존재
            dp[i] = Math.max(dp[i - 3] + drink[i - 1] + drink[i], dp[i - 2] + drink[i]);
            // 2번 연속 포도주 안먹기 가능
            dp[i] = Math.max(dp[i], dp[i - 1]);
        }
        System.out.println(dp[count]);
    }
 
}