<Algorithm> 192. 포도주시식(BJO)

1. 2156번 포도주시식(BJO)

   사용 알고리즘 : DP

• 전형적인 DP 문제, 마신 개수로 접근하다보니 통 답이 안나와서 https://limkydev.tistory.com/112 를 보고 이해를 했다.

• 보면서 조금 이해하기 어려운 부분들을 정리하면 먼저 가장 큰 틀은 i번째 와인 앞에 서있을때 최대 와인의 합이 dp[i] 이다.

• i번째 와인 앞에 서있을때 발생하는 경우의 수가 와인을 안마시는 경우(앞에서 연잔으로 마신 상황)

• 앞에 있는 와인만 마시는 경우 ( ex) 3 1 1 7 8 일때 이전의 최대치 플러스 앞의 와인을 마시는 상황 )

• 바로옆 와인과 앞에 있는 와인을 연잔으로 마시는 경우 ( ex) 3 1 1 7 8 일때 3을 마시고 가운데 두개는 건너뛰는 상황)

문제에 대한 접근&생각

1. 연속으로 최대 2개까지만 마실 수 있고 최대한 마셨을때의 최댓값 -> DP!

내 코드 

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] wine = new int[n+1];
        int[] dp = new int[n+1];
        // 해당위치의 마실수 있는 최댓값
        /************************
         * DP를 이용해 3가지 경우에 대한
         * 점화식을 세워서 최대치를 구한다.
         ************************/
        for(int i = 1; i < n+1; i++) {
            wine[i] = sc.nextInt();
        }
        if(n==1) {
            System.out.println(wine[1]);
            return;
        }
        dp[1] = wine[1];
        dp[2] = wine[1] + wine[2];
        // 2번째위치에  있을때 마시는 최댓값은 두개다 마시는 것뿐
        for(int i = 3; i < n+1; i++) {
            // 최댓값이 될수있는 3개의 후보군 
            
            // 1. 현재 위치의 wine을 안마시는 경우(바로전타임이 최댓값)
            int first = dp[i-1];
            // 2. 현재 위치의 wine을 마시는 경우 
            int second = dp[i-2]+wine[i];
            // 3. 현재 위치와 wine과 이전 위치의 wine을 마실경우
            int third = dp[i-3]+wine[i-1]+wine[i];
            
            // 3가지경우중 최댓값
            dp[i] = Math.max(third, Math.max(first, second));
        }
        System.out.println(dp[n]);
    }
}