[BOJ_2156] 포도주 시식 (java)

문제링크

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

2156번: 포도주 시식

문제설명

문제

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

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

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

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

입력

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

출력

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

제한사항

제한시간	메모리제한
2초	128MB

출처 : https://www.acmicpc.net

문제풀이

DP를 사용하여 문제를 해결할 수 있다.

포도주를 마시는데 가장 많이 마실 수 있는 방법을 구하는 문제이며, 조건으로 3잔을 연속으로 마실수는 없다.

따라서, $D_[i][j]$를 정의하면 $i$번째 잔을 마실 때 이를 $j$번 연속해서 마시는 경우라고 정의할 수 있다.

최대값을 구하기 위해서는 아래의 경우의 수를 모두 고려해야한다.

$D_[i][0] = Max(D_[i-1][0],D_[i-1][1],D_[i-2][2]$   

$D_[i][1] = D_[i-1][0] + A[i]$   

$D_[i][2] = D_[i-1][1] + A[i]$

따라서, 위 3가지를 구하여 최대값을 구해주면 문제를 해결할 수있다. (2차원의 DP)

 

그런데, 좀 더 다르게 1차원으로도 풀어볼 수 있다.

$D[i]$를 i개의 잔을 마신것 중에 최대값 이라고 정의를 하자.

그러면, 연속해서 0잔을 마시는 경우, 연속해서 1잔을 마시는 경우 연속해서 2잔을 마시는 경우를 고려하여 최대값을 넣어주면 된다.

연속해서 0잔을 마신 경우는 바로 앞에서 얼마나 마시든 상관이 없으므로 $D[i-1]$과 동일하다.

 

연속해서 1잔을 마신 경우는 $i-1$번째 잔을 마시면 안되므로, $D[i-2]$에 현재 잔인 $A[i]$를 더해주면 된다. 

 

연속해서 2잔을 마신 경우는 $i-2$번째 잔을 마시면 안되고 $i-1$번째 잔은 마셔야하므로, $D[i-3]에 $A[i] + A[i-1]$을 더해주면 된다.

 

DP를 재귀로 사용하면 시간초과가 나므로, 이번에는 for문을 사용하여 Bottom-up방식으로 구현하여주었다.

 

문제를 풀 때 나는 예외처리를 모두 해주었는데, 그냥 dp[0], dp[1], dp[2]를 정의해두고 풀면 따로 예외처리도 필요없이 간단해진다.

구현코드

//code
import java.util.Scanner;

public class Main {
    static int[] wine;
    static int[] dp = new int[10001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        wine = new int[n+1];

        for(int i = 1; i <= n; i++)
            wine[i] = sc.nextInt();

        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            int continueZero = dp[i-1];
            int continueOne = i > 1 ? dp[i-2] + wine[i] : wine[i];
            int continueTwo = i > 2 ? dp[i-3] + wine[i] + wine[i-1] : i == 2 ? wine[i] + wine[i-1] : 0;
            int max = Math.max(Math.max(continueOne,continueTwo),continueZero);
            dp[i] = max;
        }

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

 

시간복잡도

해결해야할 문제 총 n개 $O(n)$

한 문제당 걸리는 시간 $O(1)$

시간 복잡도 : $O(n)$