[JAVA] 백준, 2156번 포도주 시식

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

 

해설

3번째 와인일 때의 경우의 수

• 3번째 와인을 먹지 않는다. -> 연속하여 3번을 먹을 수 없기 때문이다.
• 2번째 와인과 3번째 와인을 연속으로 먹는다.
• 1번째 와인과 3번째 와인을 먹는다.

위의 경우의수를 3번째 와인 이상인 경우에 적용한다.

반대로 i가 3보다 작은경우는 코드를 확인하자.

코드

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

public class Main {

    static int n;
    static int[] arr;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        arr = new int[10001];
        dp = new int[10001];

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

        System.out.println(recur());
    }

    static int recur() {
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(
                // 1-2(현재 와인을 먹지 않는다), 2-3
                Math.max(dp[i - 1], dp[i - 3] + arr[i - 1] + arr[i]),
                //1-3
                dp[i - 2] + arr[i]
            );
        }

        return dp[n];
    }
}