백준 2156번 - 포도주 시식 (Java)

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

2156번: 포도주 시식

코드 :

dp - top down

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[] wine;
    static Integer[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        wine = new int[n+1];
        dp = new Integer[n+1];

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

        dp[1] = wine[1];

        if(n > 1){
            dp[2] = wine[1] + wine[2];

        }
        // dp[2]와도 비교해야 한다.
        if(n > 2){
            dp[3] = Math.max(Math.max(wine[1], wine[2]) + wine[3], dp[2]);
        }

        System.out.print(recur(n));

    }
    public static int recur(int n){
        if(dp[n] == null){
            dp[n] = Math.max(recur(n - 2), recur(n-3) + wine[n-1]) + wine[n];
            dp[n] = Math.max(dp[n], recur(n - 1));
        }
        return dp[n];
    }
}

풀이 :

내가 너무 헤맸기때문에, 되새길 겸 풀이를 썼다.

 

dp[n]을 n번째 포도주를 마셨을 때, n번째까지 마실 수 있는 포도주 양의 합이라고 해보자. n 번째를 마시는 경우이므로, 해당 상황에서 n-3까지 가능한 모든 경우의 수는 다음과 같다.

번호 \ 인덱스	n-3	n-2	n-1	n
1	x	x	o	o
2	o	x	o	o
3	x	o	x	o
4	o	o	x	o
5	o	x	x	o

o,x는 해당 인덱스를 마셨는지 여부를 말하고, 번호는 그냥 지칭하기 위해 붙였다. 이미 n번째를 마신 상태로 n은 모두 'o'임을 확인할 수 있다. 

 

여기서 기억해야 할 점은 dp[n]은 n번째 포도주를 마셨을때, 여태 마신 포도주의 최대값이라는 점이다. 따라서 dp[n]에 대한 점화식을 만들면, 해당 표에서 o인 경우(마신 상태) 점화식이 다시 적용 가능하다.

 

 

wine[n] : n번째 포도주의 양

dp[n] : n번째 포도주를 마신 상태일때, n번째까지 마실 수 있는 최대 합

recure(int n) : 재귀 함수(dp)

 

1) 표의 1, 2, 5행에 주목하면, 합의 최댓값을 구하는 것이기 때문에 2행만 생각하면 된다. dp[n] = dp[n-3] + wine[n-1] + wine[n] 을 도출해낼 수 있다. (oxoo인 경우)

dp[n] = recur(n-3) + wine[n-1] + wine[n];

여기서 주의할 점은 wine[n-1부]분에 recur[n-1]을 넣어서는 안된다. 애초에 dp[n-3]도 있기때문에, 값이 중복된다.

 

 

2) 표의 3, 4행에 주목하면, dp[n] = dp[n-2] + wine[n] 으로 생각할 수 있다. dp[n-2]가 n-2번째가 o일때까지 합의 최댓값이므로, n-3값이 달라도 한 갈래에서 나온 것으로 볼 수 있다. (ooxo인 경우)

dp[n] = (recur(n - 2) + wine[n];

 

3) 앞의 1), 2)의 결과를 비교해 더 큰값을 메모이제이션하면 된다.

dp[n] = Math.max(recur(n - 2), recur(n-3) + wine[n-1]) + wine[n];

 

4) 지금 구한 dp[n]의 값은 n번째를 마신 경우이다. n번째를 마시지 않았을 때가 더 클 수도 있다. n 대신 n-2, n-1을 먹은 경우가 더 클 수도 있다. 그래서 dp[n-1]과 값을 다시 비교해준다.

-> dp[n] = Math.max(dp[n], recur(n-1));

dp[n] = Math.max(recur(n - 2), recur(n-3) + wine[n-1]) + wine[n];
dp[n] = Math.max(dp[n], recur(n-1));

 

✓ 1)에서 recur(n-1) 대신 recure(n-3)을 써야하는 이유는 o가 두 개 연속된 상태에서(n, n-1 모두 o) n-1을 재귀하면, 정의한 dp[n]과 맞지 않는다.

 

✓ dp[3]을 초기화 할 때에도, dp[3]을 마시지 않았을 경우 더 클 수 있다는 점을 고려해야 한다. 해당 dp[n-1](3 - 1 = 2)과 비교해야한다.

 

참고 :

https://hongjw1938.tistory.com/69 외에도 많은 블로그를 본것같은데 잘 기억이 안난다. 깔끔하게 정리해주신것 같다.