[알고리즘] 백준 2156번, 포도주 시식 JAVA풀이


백준 2156번, 포도주 시식 JAVA풀이

  • 포도주가 일렬로 놓여져 있고, 다음과 같은 2가지 규칙을 지키면서 포도주를 최대한 많이 마시려고 함
  1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
  2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
  • D[i][j] = A[1] ~ A[i] 포도주
  • A[i] : i번째 잔의 양
  • i번째 잔 : 연속 j 번
  • 0번 연속 : D[n][0] = max(D[n-1][0], D[n-1][1], D[n-1[2])
  • 1번 연속 : D[n][1] = D[n-1][0] + A[n]
  • 2번 연속 : D[n][2] = D[n-1][1] + A[n]
  • D[i] = A[1], ... , A[i] 까지 포도주를 마셨을 때, 마실 수 있는 포도주의 최대 양
  • 0번 연속해서 마신 포도주 : A[i] 를 마시지 않음
  • 1번 연속해서 마신 포도주 : A[i-1] 를 마시지 않음
  • 2번 연속해서 마신 포도주 : A[i-1] 을 마시고, A[i-2] 는 마시지 않았어야 함
  • 0번 연속 : D[n-1]
  • 1번 연속 : D[n-2] + A[n]
  • 2번 연속 : D[n-3] + A[n] + A[n-1]
    static int[] a = new int[10003];
    static int[] dp = new int[10003];

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);

        int n = fs.nextInt();

        for (int i=1; i<=n; i++) {
            a[i] = fs.nextInt();
        }

        dp[1] = a[1];
        dp[2] = a[1] + a[2];

        for (int i=3; i<=n; i++) {
            dp[i] = dp[i-1];
            if (dp[i] < dp[i-2] + a[i]) {
                dp[i] = dp[i-2] + a[i];
            }
            if (dp[i] < dp[i-3] + a[i] + a[i-1]) {
                dp[i] = dp[i-3] + a[i] + a[i-1];
            }
        }

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

    }





© 2018. by HYEON

Powered by HYEON