BOJ_2156 포도주시식

계단오르기와 비슷한 문제였는데 아직 완전히 이해하지 못했던 것 같다.

연속 3잔을 마실 수 없기때문에 나올 수 있는 경우는

이렇게 3가지 경우이다. 이걸 점화식으로 나타내면

3가지 경우의 수를 비교했을 때 가장 큰 값을 dp 배열에 저장하는 방식으로 접근하면 된다. (라고 했지만 쉽게 이해가지 않아서 일일히 다써서 확인해봤다.. )

IDE 에서 디버깅 돌렸을 때 dp에는 3가지 방법 모두 고려 했을 때 가장 큰값만 저장한다.

package DynamicProgramming;

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

public class BOJ_2156 {
    static int n;
    static int[] dp;
    static int[] a;
    static BufferedReader br;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        a = new int[n + 1];
        dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(br.readLine());
        }
        dp[1] = a[1];
        if (n > 1) {
            dp[2] = a[1] + a[2];
        }
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + a[i], dp[i - 3] + a[i - 1] + a[i]));
        }
        System.out.println(dp[n]);
    }
}