[JAVA] 백준 2156 포도주_DP

 

문제 : 

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

 

 

접근 : 

 

 - 마지막 포도주를 마시는 경우와 마시지 않는 경우를 나눈다.

 

 - 만약 마지막 포도주를 마시지 않는 경우, 1) 이전까지(n-1)의 최대값이 정답이다.

 

 - 마지막 포도주를 마시는 경우, 2) 3번째 전(n-3) 최대값에 전 포도주 잔(n-1)과 이번 포도주 잔(n)을 마실 수 있다.

 

 - 또한, 3) 2번째 전(n-2) 최대값에 이번 포도주 잔(n)을 마실 수 있다.

 

 - 1) 2) 3) 3가지 경우 중 최대값을 정답으로 출력한다.

 

 

 

 

코드 구현 :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n+1];

        dp[0] = 0;
        dp[1] = Integer.parseInt(br.readLine());
        
        if(n == 1) {
            System.out.println(dp[1]);
            return;
        }

        int before = Integer.parseInt(br.readLine());
        dp[2] = dp[1] + before;

        int now;
        for(int i = 3 ; i <= n ; i++){
            now = Integer.parseInt(br.readLine());
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + before + now, dp[i-2] + now));
            before = now;
        }
        System.out.println(dp[n]);
    }
}