백준 [2156] 포도주 시식 (자바)

문제

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

풀이

연속적으로 2개를 초과하는 포도주를 선택하여 마실 수 없다.

 

i번째 포도주를 마실 때 누적합의 최대 값은 다음과 같다.

1. i-1번째까지의 누적합
2. i-2번째까지의 누적합 + i번째 값 (예: 4번째 누적합을 구한다고 가정하면 2번째 누적합(1~2까지 더한 값) + 3번째는 건너뛰고 4번째 값)
3. i-3번째까지의 누적합 + i-1번째 값 + i번째 값

위 3개의 값 중 가장 큰 값이 i번째 포도주를 마실 때 최대로 마실 수 있다.

정답코드

package com.baekjoon.p2156;

import java.io.*;

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[] arr = new int[N + 1], dp = new int[N + 1];

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

        dp[1] = arr[1];
        if (N > 1) {
            dp[2] = arr[1] + arr[2];
        }
        for (int i = 3; i <= N; i++) {
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));
        }

        System.out.print(dp[N]);
    }
}