[JAVA] 백준 (실버1) 2156번 포도주 시식

링크

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

---

문제 설명

정답률 32.669%

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

---

입력 예제

6
6
10
13
9
8
1

---

출력 예제

33

---

풀이

연속으로 3잔을 선택할 수 없으므로 연속으로 2잔씩 선택할 수 있다. 다이나믹 프로그래밍을 이용해서 문제를 해결한다. dp배열은 N번까지의 최댓값을 저장한다. 이때 N번째 와인잔이 포함되는지에 따라 구분한다.

N번째 와인잔이 포함되는 경우는 N번이 연속된 2잔에서 앞이냐 뒤냐에 따라 구분된다. 만약 5개의 잔이 있을 때 dp[5]를 구한다면 다음의 경우가 있다.

• 1, 2, 3, 4, 5
  • dp[N] = recur(N-3) + wine[N-1] + wine[N]
• 1, 2, 3, 4, 5
  • dp[N] = recur(N-2) + wine[N]

그리고 N번째 와인잔이 포함되지 않는다면 N-1번에서 재귀를 호출한다.

• 1, 2, 3, 4, 5
  • dp[N] = recur(N-1)

이렇게 해서 다음과 같이 재귀 함수를 생성할 수 있다.

static int recur(int N) {

    if (dp[N] == null) {
        //N번이 포함될 때
        int included = Math.max(
                recur(N - 2) + wine[N],  //N-2번까지와 N번의 합
                recur(N - 3) + wine[N - 1] + wine[N]);  //N-3번까지와 N-1, N번의 합
        //N번이 포함되지 않을 때
        int notIncluded = recur(N - 1);
        dp[N] = Math.max(included, notIncluded);
    }
    
    return dp[N];
}

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
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 {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i = 1; i <= N; i++) {
            wine[i] = Integer.parseInt(br.readLine());
        }
        //N이 1일 때
        if (N == 1) {
            System.out.println(wine[1]);
            return;
        }

        dp[0] = 0;
        dp[1] = wine[1];
        dp[2] = wine[1] + wine[2];  //dp는 N번까지의 최댓값

        System.out.println(recur(N));
    }

    static int recur(int N) {

        if (dp[N] == null) {
            //N번이 포함될 때
            int included = Math.max(
                    recur(N - 2) + wine[N],  //N-2번까지와 N번의 합
                    recur(N - 3) + wine[N - 1] + wine[N]);  //N-3번까지와 N-1, N번의 합
            //N번이 포함되지 않을 때
            int notIncluded = recur(N - 1);
            dp[N] = Math.max(included, notIncluded);
        }

        return dp[N];
    }
}