포도주 시식 ( 백준 2156 )

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

 

* 포도주를 최대한 많이 마셔야 하는 상황

* 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 함

* 연속으로 놓여 있는 3잔을 모두 마실 수는 없음

* 위 조건에 맞추어서 1-n까지의 번호가 붙어 있는 n개의 포도주 잔이 존재하고 최대한 많은 양을 마셔야 함

 

* 순서대로 마셔야 하니까 정렬, 그리디 보다는 dp라고 생각했다

* 문제에 안마셔야 하는 법은 안적혀 있어서 무조건 마셔야 하는 경우만 생각했다.( 좀 이상한데...? )

* 그러면 아래와 같은 점화식이 도출된다.

* 초기값

-dp[0] : 첫번째 포도주 시식

-dp[1] : 첫번째 포도주 + 두번째 포도주 시식

-dp[2] : 첫번째 포도주+두번째 포도주, 첫번째 포도주+세번째 포도주, 두번째 포도주+세번째 포도주 의 최댓값

(3번 연속해서 안마시면됨)

 

* 점화식

- dp[i-1] : 현재 포도주를 제외한 전 포도주 까지의 최대값

- dp[i-2] + grape[i] : 현재 포도주를 포함하고 전전 포도주의 최대값을 더한 값

- dp[i-3] + grape[i-1] + grape[i] : 현재 포도주를 포함하고, 전 포도주까지 포함하고 전전전까지 포도주의 최대값을 더한 값

의 최대값. (  처음에 포함을 못 시켰는데, 전 포도주가 포함된 값이 최대값이 될수도 있어서 포함시켜야 한다. )

 

코드

import java.io.*;
import java.util.*;

public class BOJ2156 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        int[] grape = new int[size];
        int[] dp = new int[size];

        for(int i = 0; i < size; i++) {
            grape[i] = Integer.parseInt(br.readLine());
        }
        dp[0] = grape[0];
        if(size > 1) dp[1] = grape[0]+grape[1];
        if(size > 2) dp[2] = Math.max(Math.max(grape[0]+grape[1], grape[0]+grape[2]), grape[1]+grape[2]);

        for(int i = 3; i < size; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(grape[i]+grape[i-1]+dp[i-3], grape[i]+dp[i-2]));
        }
        System.out.println(dp[size - 1]);
    }
}

 

* 초기값을 신경써서 구하고, 점화식을 잘 세우면 쉬운 dp는 풀리는거 같다.