백준 2156번 포도주 시식(java)

[Silver I] 포도주 시식 - 2156

문제 링크

성능 요약

메모리: 16028 KB, 시간: 132 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 10일 14:26:41

문제 설명

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

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

출력

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

풀이

100	100	0	0	100	100
1	2	3	4	5	6

4번에 도달할 수 있는 경우의 수를 찾아보자,

 

우선 연속으로 세 개를 선택하는 건 불가능하다 !

 

그러므로 3번을 선택하는 경우와 2번을 선택하는 경우로 나눴을 때

 

3번을 선택한다면 자동으로 1 -> 3 -> 4의 루트가 만들어진다. 

 

2번을 선택한다면 자동으로 1 -> 2 -> 4의 루트가 만들어진다.

 

연속으로 세 개를 선택하는 건 불가능 하기때문이다 !

 

그럼 한 컬럼에 도달할 수 있는 분기는 두 개로 나눠진다.

 

x = x-1 + x-3    or     x = x-2

 

다만 우리는 누적합을 구해야 하므로

 

x = x-1 + dp[x-3]  +  x  or  x = dp[x-2]  + x 로 점화식을 만들 수 있다 !

 

다만 이렇게 점화식을 끝낸다면 문제가 발생한다.

 

바로 두 칸을 건너 뛰는 경우의 수를 고려하지 않았기 때문이다

 

100	100	0	0	100	100
1	2	3	4	5	6

 

이 예시를 다시 살펴보자

 

위의 점화식으로 문제를 해결하려 하면 위의 테이블에서 최댓값은 300이 나오게 된다.

 

왜냐하면, 100->100 -> 0 ->100 또는 100 -> 0 ->100->100 이런 식으로 0 하나를 무조건 포함하기 때문이다.

 

그렇다 위의 점화식에는 한 칸을 건너 뛰는 식은 포함돼 있지만 두 칸을 건너뛰는 식은 포함돼있지 않다.

 

연속으로 세 개를 고를 수 없는 것이라는 조건을 다시 한 번 생각해봐야한다.

 

만약 

100

100

1

1

1

100

100

 

이라는 테이블이 있다면 100은 무조건 다 포함시켜야 한다.

 

그리고 세 개를 연속 선택하지 않기 위해 가운데 1만 선택할 것이다.

 

이를 통해 연속으로 뛰어 넘을 수 있는 최대 갯수는 2칸이라는 것을 알 수 있다.

 

그럼 2칸을 뛰어 넘는 조건만 점화식에 추가해주면 된다.

 

x = x - 4 + x - 1 과 같다.

 

이를 누적합으로 표현한다면, dp[x] = (dp[x-4] + x-1) + x 와 같다.

 

그럼 점화식은 다음과 같이 변한다.

 

x = MAX ((x-4 + x-1) or (x-3 + x-1) or (x-3 + x-2) )  + x

 

이제 코드로 구현해보자

 

전체코드

public class Main {
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int dp[] = new int[N+3];
        int x[] = new int[N+3];
        x[0] = 0;
        for(int  i = 1 ;i<=N;i++){
            x[i] = Integer.parseInt(br.readLine());
        }

        dp[0] = 0;
        dp[1] = x[1];
        dp[2] = x[1] + x[2];
        dp[3] = Math.max(x[2], x[1]) + x[3];

        int max = Math.max(dp[2], dp[3]);

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

        bw.write(max + "");
        bw.flush();
    }
}