[백준 2156] - [다이나믹프로그래밍] - 포도주 시식 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/2156

---

이 문제는 다이나믹 프로그래밍 (DP) 으로 접근 하면 된다.

다이나믹 프로그래밍에서 제일 중요한건 점화식이다.

같은 규칙으로 계산이 되고 그 규칙을 찾고 찾은 규칙에서 점화식을 구하면 문제는 아주 쉽게 풀린다.

모든 DP 문제는 점화식 구하는게 일이다.

이 문제에서 제공하는 조건은 두가지가 있다.

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

일단 첫번째 조건은 한 잔에 들어 있는 포도주를 찔끔찔끔 마실수 없다는걸 말하는 거고 

두번째 조건은 연속으로 3잔을 마실수 없다는걸 말한다.

이 두번째 조건이 점화식을 구하는데 어려움을 느끼게 한다. 

A B C 세 포도주 잔이 있을때  (A, B), (A, C) , (B, C) , ( A ) , ( B ) , ( C )  이렇게 마실수 있다는거겠다.

(A, B, C) 이렇게만 마시지만 않으면 된다. 

문제에서 제공하는 조건을 이해했으니 이제 점화식을 구해볼 차례이다. 

본인은 문제를 풀면서 3가지 상황을 만들었다. 

각i 번째 최대 포도주 양은 정수형 배열 dp 에 저장했고

각 포도주의 양 자체는 정수형 배열 arr에 저장했다.  

순서 i 번째 포도주 잔에 도달 했을때 상황

1. i 번째 포도주 잔은 마시지 않는다.

2. i 번째 포도주 잔을 첫번째 잔으로 마신다.

3. i 번째 포도주 잔을 두번째 잔으로 마신다.

첫번째 상황에 올 수 있는 점화식을 구해보자

i-1 번째 잔이 두번째 잔으로 마셨을 경우도 있고, i-1 번째 잔 조차도 안 마셨을 경우도 있고 여러 조건이 있지만 그럼에도 이전 포도주 잔까지 마셨던 최대 포도주의 양이 1번 상황에서는 맞을 것이다.

첫번째 상황에 대한 점화식은 아래와 같이 만들었다.

dp[i-1]

두번째 상황에 올 수 있는 점화식을 구해보자

상황은 어찌 됐든 바로 앞에 있는 i-1 번째 포도주 잔은 건들지 않았다는 말이 된다. 

i-1 번째 포도주 잔을 마셨다면 두번째 상황이 될 수 없느니깐, i-2 번째 마신 최대 포도주 양에 i 번째 포도주 양을 더해야 할 것이다.

두번째 상황에 대한 점화식은 아래와 같이 만들었다.

dp[i-2] + arr[i]

세번째 상황에 올 수 있는 점화식을 구해보자.

이 세번째 상황 떄문에 문제를 두번 제출헀다가 틀렸다는 결과를 받았다. 

넓게 생각해보면 간단하다 i-1 잔은 무조건 마셔야 하고 i 번째 잔도 마셔야 한다. 

그럼? 

i-2 번째 잔은 건들면 안되니깐 i-3 번째 까지 마신 최대 포도주양에 i-1 번째와 i 번째 포도주 잔의 각 포도주 양을 더하면 될 것이다.

세번째 상황에 대한 점화식은 아래와 같이 만들었다.

dp[i-3] + arr[i-1] + arr[i]

점화식을 구하니 문제는 다 풀렸다 점화식을 토대로 소스를 작성하고 제출하면 된다.

이 문제를 풀면서 여러가지 반례가 필요할텐데 제일 간단한 반례 두개만 만족하면된다. 

기본 예제로 나온 6 6 10 13 9 8 1 정답 33 이 경우를 먼저 풀고

6 100 0 100 0 100 0  정담 300 이 문제를 풀어보면 된다.

점화식을 잘못 작성하였다면 두번쩨 반례에서는 200이 나올거다. 

문제를 이해할때 무조건 앞뒤 전부 선택해야 된다 라는 고정관념에 묶여 있으면 안된다.

한 잔 띄고 한 잔 띄고 한 잔 띄고 이렇게 마실 수도 있고 한 잔 만 마실 수도 있고 여러 가지로 문제에서 제공하는 조건 안에서 자유롭게 마실 수 있다는걸 잊으면 안된다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static int[] arr;
    public static int[] dp;
    public static int result;
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int count = Integer.parseInt(br.readLine());
        
        arr = new int[count+3];
        dp = new int[count+3];
        
        for(int i=0; i < count; i++) {
            arr[3+i] = Integer.parseInt(br.readLine());
        }
        
        for(int i=3; i < arr.length; i++) {
            int dont_sel = dp[i-1];
            int fron_sel = dp[i-2] + arr[i];
            int last_sel = dp[i-3] + arr[i-1] + arr[i];
            result = Math.max(dont_sel, Math.max(fron_sel, last_sel));
            dp[i] = result;
        }
        System.out.println(result);
    }
}