[백준] 2156번 - 포도주 시식

 

2156번: 포도주 시식

 

 

 

1부터 n번까지 번호가 붙여져 있는 포도주를 1번 -> n번 방향으로 마시는데 연속으로 놓인 잔을 최대 2잔까지만 마실 수 있을 때 마신 포도주 총량의 최대를 구하는 문제이다.

 

문제 해결을 위한 점화식을 말로 풀어쓰면 다음과 같다. 

눈여겨 봐야 하는 조건은 연속으로 놓여 있는 3잔을 모두 마실 수 없다는 조건이다. 따라서 x번째에 놓인 포도주까지 마셨을 때 마신 포도주의 총량의 최대는 다음 i-i, i-ii, ii-i 세 경우 중 하나이다.

 

i) x번째 포도주를 마시는 경우 (i-i, i-ii 에 x번째 포도주의 양을 더해준다.)

    i-i) x-2번째 포도주를 마시지 않고 x-1번째 포도주를 마셨을 때 마신 포도주 총량의 최대

    i-ii) x-2번째까지 포도주를 마셨을 때 마신 포도주 총량의 최대

ii) x번째 포도주를 마시지 않은 경우

    ii-i) x-1번째 까지 마신 포도주 총량의 최대

 

 n번째 잔에 담긴 포도주 양을 wines[i]라고 하고 포도주 glass잔까지 마신 경우 포도주 총량의 최대를 반환하는 함수를 drinkWine이라고 할 때,

i-i) == drinkWine(glass-3) + wines[glass-1] + wines[glass]

i-ii) == drinkWine(glass-2) + wines[glass]

ii-i) == drinkWine(glass-1)

이다.

static int drinkWine (int glass) {
        
    // 1잔 이하를 마신 경우에 대해 분기처리를 하여 재귀함수를 종료시킨다.
    if (glass == 1) return wines[1];
    if (glass <= 0) return 0;
	
    return Math.max(drinkWine(glass-1), Math.max(drinkWine(glass-3) + wines[glass-1], drinkWine(glass-2)) + wines[glass]);
}

 

 

간과하면 안되는 부분은 입력으로 주어지는 포도주 잔의 최대 개수가 10,000개라는 것이다. drinkWine 함수는 glass-3, glass-2, glass-1에 대한 자기 함수를 계속해서 호출하므로 그냥 사용하게 되면 x번째 포도주까지 마셨을 때의 최대값을 매번 계산하게 된다. 따라서 한 번 연산한 결과를  메모제이션하여 재사용할 수 있는 다이나믹프로그래밍을 사용하여 시간복잡도를 선형적으로 O(n) 바꿀 수 있다.

 

 

 

 

전체 코드

import java.io.*;

public class Main {
    
    static int N, wines[];
    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());
        wines = new int[N+1];
        dp = new Integer[N+1];
        
        for (int i=1; i<=N; i++) wines[i] = Integer.parseInt(br.readLine());
        
        System.out.println(drinkWine(N));
        
        br.close();
    }
    
    static int drinkWine (int glass) {
        
        if (glass == 1) return wines[1];
        if (glass <= 0) return 0;
        
        if (dp[glass] == null) 
        	dp[glass] = Math.max(drinkWine(glass-1), Math.max(drinkWine(glass-3) + wines[glass-1], drinkWine(glass-2)) + wines[glass]);
        
        return dp[glass];
    }
}