[BOJ] 백준 2156 포도주 시식

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

 Input 

6

6

10

13

9

8

1

 

 Output 

33

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

* 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

    O    O    X

    X    O    O

    O    X    O

wine[i] ; i 번째 포도잔에 들어있는 포도주의 양(비용)

dp[i] = Max(dp[i-1],  wine[i] + wine[i-1] + dp[i-3], wine[i] + dp[i-2])

            i 번째 포도잔까지의 최대로 마신 양(비용)

 

① i 번째 포도주를 먹지 않았을 경우

    → ( i-1번째에서 새로 확인.)

② i 번째 포도주와 i-1번째 포도주를 마신 경우

    → (i와 i-1번째 값을 포함하고 i-3번째에서 새로 확인)

③ i번째 포도주를 마시고 i-1번째를 안 마신 경우

    → (i번째 값을 포함하고 i-2번째에서 새로 확인)

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
         
        // 인덱스를 1부터하기 위함
        int[] wine = new int[n+1];
        int[] dp = new int[n+1];
         
        // 포도주 양(비용) 입력
        for(int i=1; i<=n; i++) {
            wine[i] = Integer.parseInt(sc.next());
        }
         
        dp[0] = 0;
        dp[1] = wine[1];
         
        if(n > 1) { // 포도잔이 최소 2개
            dp[2] = wine[1] + wine[2];
        }
 
        for(int i=3 ; i<=n ; i++) {
            dp[i] = Max( dp[i-1], wine[i] + wine[i-1] + dp[i-3], wine[i] + dp[i-2]);
        }
         
        System.out.println(dp[n]);
 
    }
 
    private static int Max(int...arr) {
        int result = arr[0];
        for(int i=1; i<arr.length; i++) {
            result = result > arr[i] ? result : arr[i];
        }
        return result;
    }
}