[백준] 2156번 : 포도주 시식

문제

 

 

접근 방식

가장 많은 양의 포도주를 마실 수 있는 경우를 찾아야 하는데

두 번째 조건을 보면 연속으로 마실 수 있는 포도주는 두 잔까지고

이는 1,2번째 잔을 마셨다면 3번째 잔은 건너뛰고

4,5,6,...n번째 포도주 중 하나를 먹어야 한다는 말이다.

 

거꾸로 생각해 보면 두 잔을 연속으로 마실 때는 이전 잔을 무조건 마셨다는 것이 되고

한 잔만 마셨을 때는 바로 이전 잔을 제외한 이전의 어떠한 잔들 중 하나 이상은 마신 것이 된다.

 

만약 n번째 잔을 마실 때, 해당 잔이 연속으로 두 번째 마시고 있는 잔이라면

(n번 잔의 양 + n-1번 잔을 첫 번째로 마신 경우의 최댓값) 이 해당 경우의 최댓값이 되고

해당 잔이 연속이 아닌 첫 번째로 마시고 있는 잔이라면

n-2 이하 번의 잔의 최댓값 + n번 잔의 양이 최댓값이 된다.

 

점화식을 정리하면 다음과 같다.

dp[n][한 잔을 연속으로 마신 경우] = dp[n-2][누적 최댓값] + n번 잔의 양
dp[n][두 잔을 연속으로 마신 경우] = dp[n-1][한 잔을 연속으로 마신 경우] + n번 잔의 양
dp[n][누적 최댓값] = max(dp[n-1][누적 최댓값], dp[n][한 잔을 연속으로 마신 경우], dp[n][두 잔을 연속으로 마신 경우])

 

 

풀이

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[] cups = new int[n + 1];
        int[][] dp = new int[n + 1][3];

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

        dp[1][0] = cups[1];
        dp[1][2] = cups[1];

        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 2][2] + cups[i];
            dp[i][1] = dp[i - 1][0] + cups[i];
            dp[i][2] = Math.max(dp[i - 1][2], Math.max(dp[i][0], dp[i][1]));
        }

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