[PS] BOJ2156 포도주 시식 ( DP ) with JAVA,Python

2156번: 포도주 시식

 

◎ 문제풀이

 

일렬로 나열된 와인을 마실 때, 최대 비용으로 마시는 경우를 구하는 문제이다. 단, 연속으로 3잔을 마시지 못한다.  와인의 모든 경우를 따져서 최대 비용을 구하는 문제이니 메모리제이션을 활용한 DP로 풀어주는 것이 좋다. DP로 풀려면 점화식을 구해야 한다. 

 

 

 

 

와인 3잔이 있다. 와인은 마시거나 안 마시거나 2가지 경우를 선택할 수 있다. 그럼 총 8가지 경우의 수가 나온다.

 

1) O O O

2) O O X

3) O X O

4) X O O

5) X X O

6) X O X

7) O X X

8) X X X

 

경우를 조건에 따라 필터링 해보자. 조건은 2가지가 있다.

 

1) 와인은 3잔 연속으로 마시지 못한다.

2) 최대 비용으로 마시는 경우를 구하라

 

1) O O O : 3잔 연속으로 못 마심

2) O O X

3) O X O

4) X O O

5) X X O : 최대비용이 아님

6) X O X : 최대비용이 아님

7) O X X : 최대비용이 아님 

8) X X X : 최대비용이 아님

 

와인을 마시는 것은 음의 비용이 아니다. 양의 비용이다. 3잔 중 1잔을 마시는 경우는 3잔 중 2잔을 마시는 경우보다 항상 작다. 그러므로 경우의 수는 3가지로 좁혀진다. 

 

1) O O X

2) O X O

3) X O O

 

3가지 경우 중에 최댓값을 구해야 한다.  그럼 여기에 메모리제이션 개념을 넣어보자. 

 

 

1) O O X

 

 

 

와인은 양의 비용이므로 마지막 잔을 안 마신다는 의미는 1부터 N-1까지 마신 경우의 최댓값이 1부터 N까지 마신 경우의 최대를 의미한다.

 

dp[n] = dp[n-1] 

 

2) O X O

 

 

N-1번째 와인을 안 마신다는 의미는 1부터 N-2번째까지 마신 경우의 최대값에 N번째 와인을 마신 양의 비용의 합을 의미한다. 

 

dp[n] = dp[n-2] + wines[n]

 

3) X O O

 

 

N-1번째 와인을 안 마신다는 의미는 1부터 N-3번째까지 마신 경우의 최댓값에 N-1,N번째 와인을 마신 양의 비용의 합을 의미한다.

 

dp[n] = dp[n-3] + wines[n-1] + wines[n]

 

 

3가지 경우 중 최댓값이 dp[n]이 된다.(메모리제이션) 정리하면, 이 문제는 양의 비용을 가진 수열에서 최대비용을 구할 때의 경우를 도출할 수 있는지를 물어보는 문제였다. 그럼 코드로 구현해보자. 

 

 

◎ 코드

 

JAVA 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import static java.lang.Math.*;

//BOJ2156 포도주 시식
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[] wines = new int[n+1];
        int[] dp = new int[n+1];

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

        dp[1] = wines[1];
        if(n>=2) dp[2] = wines[1] + wines[2]; // n이 2보다 경우!!

        for(int i=3;i<=n;i++){
            //OOX
            int case1 = dp[i-1];
            //OXO
            int case2 = dp[i-2] + wines[i];
            //XOO
            int case3 = dp[i-3] + wines[i-1] + wines[i];

            dp[i] = max(case1,max(case2,case3)); // 3가지 경우 중 최댓값
        }

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

    }
}

 

 

Python 풀이

# 연속된 3잔을 모두 마실수 없다. 
# 많은 양의 포도주를 맛보고 싶다. ( 개 X )
# boj2156 포도주 시식

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

answer = 0
n = int(input())
arr = [0] * (n+1)
dp = [0] * (n+1)

for i in range(1,n+1) :
    arr[i] = int(input())
  
dp[1] = arr[1]
if n >= 2 : dp[2] = arr[1] + arr[2]

for i in range(3,n+1):
    
    #OOX : i번째 와인을 안 마셨다면, i-1번째 경우의 최대값이 최대가 된다. 
    case1 = dp[i-1]
    #0X0 : i번째 와인을 마시고, i-1번째 와인을 안 마신다면, i-1번째 경우의 최대값 + i번째 와인의 양이 최대가 된다.
    case2 = dp[i-2] + arr[i]
    #X00 : i번째 와인을 마시고, i-1번째 와인을 마시고, i-2번째 와인을 안 마신다면, i-3번째 경우의 최대값 + i-1,i번째 와인의 양이 최대가 된다.
    case3 = dp[i-3] + arr[i-1] + arr[i]

    dp[i] = max(case1,case2,case3)

print(dp[n])

 

 

 

참고용 DFS 파이썬 풀이 ( 시간초과 )

 

포도주를 마시는 경우와 마시지 않는 경우가 있으니 DFS로 탐색하면 된다고 생각했다. 그러나 그렇게 계산하면, 시간복잡도가 O(2가지 경우 ^ n)이고 n은 최대 10,000이니, 최대 2^10,000 연산을 하게 되어 시간초과가 발생한다.  그러니 DP를 이용하여 문제를 접근해야 한다. 

 

# 연속된 3잔을 모두 마실수 없다. 
# 많은 양의 포도주를 맛보고 싶다. ( 개 X )
# DFS 마시는 경우, 마시지 않는 경우 ( 연속 카운트 )


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

answer = 0
n = int(input())
arr = []

for _ in range(n) :
    arr.append(int(input()))
  
def dfs(arr,sum,idx,sequence_count) :

    global answer

    #탈출조건
    if idx == n :
        answer = max(answer,sum)
        return
    
    # 와인을 마시는 경우
    if(sequence_count < 2) : dfs(arr,sum+arr[idx],idx+1,sequence_count+1)

    # 와인을 마시지 않는 경우
    dfs(arr,sum,idx+1,0)


dfs(arr,0,0,0)
print(answer)