이것저것 개발 블로그

https://acmicpc.net/problem/2156

풀이)

import java.util.Scanner;

public class Main_BJ_2156_포도주시식 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] grape = new int[n+1];
        for(int i=1; i<=n; i++)
            grape[i] =  sc.nextInt();
        int[] dp = new int[n+1];

        dp[1] = grape[1];
        if(n>=2)
            dp[2] = grape[1]+grape[2];
        for(int i=3; i<=n; i++)
            dp[i] = Math.max(Math.max(dp[i-1], dp[i-2]+grape[i]), dp[i-3]+grape[i-1]+grape[i]);

        System.out.println(dp[n]);
    }//main
}

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

이 문제와 비슷하다!

하지만 이 문제는 무조건 맨 마지막 계단을 밟아야 한다는 조건이 있고, 이 문제는 그렇지 않다는 부분이 다르다.

따라서 비슷하게 가되, 3가지 경우를 비교해야한다.

1. 현재 잔(i) + 직전 잔(i-1) + 3번째 전까지 최대(dp[i-3])

2. 현재 잔 + 2번째 전까지 최대

3. 1번째 전까지 최대

이렇게 하면 쉽게 구할 수 있다!(하지만 난 틀림ㅠ)