[PS] 백준 2156번 포도주 시식 - DP

문제

예제

풀이

풀다가 영 감이 안와서
이전 문제에서 참고했던 블로그가 이해하기 쉽게 코드를 짜여있길래 또 참고한 풀이

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        int[] arr = new int[n+1];
        int[] dp = new int[n+1];

        for(int i=1; i<=n; i++) {
            arr[i] = in.nextInt();
        }

        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.println(dp[n]);

    }
}