[백준(baekjoon) 2156] 포도주 시식

문제

백준 2156

n(1…10,000)개의 포도주가 있고 각 값이 주어진다.
포도주 선택 시 한잔을 모두 마셔야 하고, 연속으로 최대 2잔 마실 수 있을 때 최대 값을 구하라.

• 예시 : n = 6 { 6, 10, 13, 9, 8, 1 }
  => 정답은 1, 2, 4, 5{O, O, X, O, O, X}를 선택 할 때 33으로 최대다.
• 주의 : 각 포도잔의 값은 음이 아닌 정수이다.

해결

DP로 풀어야 한다는 전제하에 진행하였다. 난 DP 연습을 하고 있기 때문에.
단순하게 O, X 형식으로 하면 2^10000으로 2초를 훌쩍 넘긴다..!

그 다음에 여러 시도를 해봤었는데, (아래와 같은 것들?) 모두 시간초과가 떴다..

1. 3개씩 묶으면 그 안에 무조건 X하나가 나와야 하므로 n/3만큼 각 경우를 구해 DP로 푸는 법
2. X는 최대 2개 연속 가능, 총 X의 개수는 n/3 + 1만큼이다.를 활용해 수를 줄이는 법

시간이 없으신 분들은 여기서 부터…!

각 포도잔은 두 가지로 나눌 수 있고, 이러한 규칙을 가지고 있다.

1. 안 마시는 경우 (X)
   
   • 연속으로 마시는 경우를 고려하지 않아도 된다.
   • 즉, 이전 잔(O, X 중)에서 큰 값을 선택하면 된다.
2. 마시는 경우 (O)
   
   • 1) 이전 값이 O인 경우 : {X, O, O(자신)}
     
     • 연속으로 O이기 때문에 두번째 전 값이 X이다.
   • 2) 이전 값이 X인 경우 : {?, X, O(자신)}
     
     • 자신이 첫번째 O이기 때문에, 두번째 전 값은 중요치 않다.
   • 1), 2) 각각의 합을 구해 큰 값을 골라 선택한다.

즉, 이를 활용해 정답을 구하면 된다.

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

1. Top-Down 방식

접근하기 편하게 index = 1;로 했다.

1.import java.util.*;
2.
3.public class Main {
4.    static int[] input;
5.    static long[][] dp;
6.    public static void main(String[] args) {
7.        Scanner sc = new Scanner(System.in);
8.        int n = sc.nextInt();
9.        input = new int[n + 1];
10.        dp = new long[n + 1][2];
11.
12.        for (int i = 1; i <= n; i++) input[i] = sc.nextInt();
13.        dp[n] = goTo(n);
14.        System.out.println(Math.max(dp[n][0], dp[n][1]));
15.    }
16.
17.    public static long[] goTo (int n) {
18.        if (n == 1) return new long[] {0, input[1]};
19.        else if (n == 2) return new long[] {input[1], input[1] + input[2]};
20.
21.        dp[n - 1] = goTo(n - 1);
22.        long[] current = new long[2];
23.        current[0] = Math.max(dp[n - 1][0], dp[n - 1][1]);
24.        current[1] = input[n] + Math.max(dp[n - 2][0] + input[n - 1], dp[n - 1][0]);
25.
26.        return current;
27.    }
28.}

2. Bottom-Up 방식

여기는 index = 0;으로 했다.

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = sc.nextInt();
7.        int[] input = new int[n];
8.        long[][] dp = new long[n][2];
9.
10.        for (int i = 0; i < n; i++) {
11.            input[i] = sc.nextInt();
12.            if (i == 0) dp[0][1] = input[i];
13.            else if (i == 1) {
14.                dp[1][0] = input[i-1];
15.                dp[1][1] = input[i-1] + input[i];
16.            } else {
17.              dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
18.              dp[i][1] = input[i] + Math.max(dp[i-2][0] + input[i-1], dp[i-1][0]);
19.            }
20.        }
21.        System.out.println(Math.max(dp[n-1][0], dp[n-1][1]));
22.    }
23.}

결과

1. Top-Down 방식
2. Bottom-Up 방식