[BOJ] 2156 (포도주 시식) - Java

PS공부를 한지 한달정도 됐는데 깃허브에 올려놓은 코드들을 일일이 찾아서 복기하기도 귀찮고.. 해서 티스토리에 정리해보려한다.

 

문제 링크 : 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 이하의 음이 아닌 정수이다.

 

[출력]

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

 

[풀이 및 느낀점]

우선 DP가 다른 알고리즘들에 비해서 좀 고난이도?라는 생각이 든다.

 

무지성 BFS, 백트래킹으로 조져대다가 점화식 세우는 문제가 나오니 머리가 너무아프다ㅜ

 

문제에서 3잔 연속 마실 수 없다고 했는데 이 경우는 3가지로 나눌 수 있다.

여기서 i-2, i-1, i 순서이다.

1. 첫잔을 마시지 않고 두잔 연속마시는 경우(XOO)

이 경우는 첫잔을 마시지 않았으니 첫잔 이전의 누적값(맨 오른쪽이 현재 잔) dp[i-3]을 더해준다 -> dp[i-3]은 맨 왼쪽 잔을 마시기 이전의 누적값이기 때문이다.

그리고 두번째 잔의 이전 누적값이 없기 때문에 arr[i-1], 즉 이전값과 현재값또한 누적값이 없는 상태이기 때문에 arr[i]를 더해준다.

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

 

2. 두번째 잔을 마시지 않는 경우(OXO)

이번엔 맨 왼쪽잔과 맨 오른쪽잔(현재)를 마시는 경우인데, 맨 왼쪽잔을 마신다 -> dp[i-2]가 이전의 누적값이기 때문에 더해주고, 현재 잔을 마시면 arr[i]를 더해주면 된다.

>> dp[i-2] + arr[i]

 

3. 세번째 잔을 마시지 않는 경우(OOX)

마지막 경우는 쉽다. 이전까지 마셔와서 누적값이 쌓여있을 것이기 때문에 dp[i-1]만 해주면 현재 잔 이전의 누적값을 알 수 있다.

>>dp[i-1]

 

이렇게 나온 3가지 경우들에 대해서 최댓값을 얻어야 하기 때문에 Math.max 함수를 이용해서 각각의 값들을 전부 비교해주면 된다.

 

대신 for문이 3부터 시작한다는 것은 잔이 1잔 또는 2잔인 경우에 알아서 예외처리를 해줘야 되기때문에

n >=1 인 경우와 n>=2인 경우를 따로 나눠줬다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2156 {
    static int n;
    static int[] arr;
    static int[] dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());

        arr = new int[n+1];
        dp =  new int[n+1];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 0;
        if(n >= 1)
            dp[1] = arr[1];
        if(n >= 2)
            dp[2] = dp[1] + arr[2];
        System.out.println(solve(n));
    }
    public static int solve(int n){
        if(dp[n] == 0){
            for(int i=3;i<=n;i++){
                dp[i] = Math.max( Math.max(dp[i-1], dp[i-3]+arr[i-1]+arr[i]), dp[i-2]+arr[i]);
                // xoo : dp[i-3] + arr[i-1] + arr[i]
                // oxo : dp[i-2] + arr[i]
                // oox : dp[i-1]
            }
        }

        return dp[n];
    }
}