백준 2156 (포도주 시식) - java

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

연속으로 놓여 있는 3잔을 모두 마실 수 없다. 그러므로 연속으로 마실수 있는 포도주는 1개거나 2개이다.

dp[n][3] 을 선언하여 dp[1] 은 해당 번째 맥주가 처음연속인 경우 , dp[2] 는 해당 맥주가 2번째 연속인 경우의 최댓값이다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int n= 0;
    static int[] board = new int[10001];
    static int[][] dp = new int[10001][3];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        for(int i=1;i<=n;i++)
        {
            board[i] = Integer.parseInt(br.readLine());
        }

        if(n==1)
        {
            System.out.println(board[1]);
        }
        else if(n==2)
        {
            System.out.println(board[1]+board[2]);
        }

        else {
            dp[1][1] = board[1];
            dp[1][2] = 0;

            dp[2][1] = board[2];
            dp[2][2] = board[1]+board[2];
            int max = 0;
            for(int i=3;i<=n;i++)
            {
                // 해당 맥주가 처음 연속이기 위해서는 2번째 전 차례 맥주의 최댓값에 해당 맥주를 마시는 경우
                dp[i][1] = Math.max(dp[i-2][2],dp[i-2][1])+board[i];
                
                // 해당 맥주가 2번째 연속인 경우는 바로 전 차례에 2개를 연속으로 마신 경우와
                // 바로 전 차례에 한개를 연속해서 마시고 지금 맥주를 마시는 경우 중 최댓값
                dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+board[i]);
                
                // 2가지 경우 중 최댓값
                int tmp = Math.max(dp[i][1],dp[i][2]);
                
                // 갱신
                max = Math.max(tmp,max);
            }
            System.out.println(max);
        }
        br.close();
    }
}