백준 2156번 (DP) : 포도주 시식 (JAVA) 문제 풀이

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

2156번: 포도주 시식

---

 

✏️ 문제

---

 

🔐 문제 해결

나란히 놓여있는 포도주를 마셔서 가장 많이 마신 양을 출력하면 되는 문제입니다.

 

이 문제를 보면서 계단오르기 문제와 유사하여 해당 문제 풀이 방식대로 푼다면 틀리게 됩니다.

이번 문제에는 포도주를 마시지 않는 경우도 있을 수 있으므로, 해당 경우도 잘 생각해줘야 합니다.

 

문제에서 주어진 예제를 살펴보면, 가장 많이 마실 수 있는 방법은 아래와 같을 것입니다.

첫 번째, 두 번째, 네 번째, 다섯 번째를 선택하게 되면 33이 됩니다.

아래에서 정확한 풀이를 설명 해보겠습니다.

 

1. 테이블 정의

먼저 연속해서 3잔을 마실 수 없는 조건이 있으므로 2차원 배열이 필요합니다.

int[][] dp = new int[N][3];

테이블을 아래와 같이 세 가지로 생각해볼 수 있습니다.

• dp[i][0]은 현재 i번째 포도주를 마시지 않은 상태를 뜻합니다.
• dp[i][1]은 현재 i 번째 포도주를 마시고, i 번째 포도주를 포함해서 연속해서 1잔 마셨다는 뜻입니다.
• dp[i][2]은 현재 i 번째 포도주를 마시고, i 번째 포도주를 포함해서 연속해서 2잔 마셨다는 뜻입니다.

 

2. 점화식 찾기

 

dp[i][0] 먼저 생각해보겠습니다.

• 현재 i 번째 포도주를 마시지 않습니다.
• 아래 세 가지 값 중 가장 큰 값을 찾아서 넣어주도록 합니다.
  • i-1 번째 포도주를 마시고, 연속해서 1잔을 마신 경우 : dp[i-1][1]
  • i-1 번째 포도주를 마시고, 연속해서 2잔을 마신 경우 : dp[i-1][2]

 

식으로 표현하면 아래와 같습니다.

dp[i][0] = Math.max(dp[i-1][1], dp[i-1][2]);

 

다음은 dp[i][1] 에 대해 생각해보겠습니다.

• 현재 i 번째 포도주를 마셨고, 현재 포도주를 포함해서 연속으로 1잔을 마신 상태입니다.
• 그렇다면 i-1 번째 포도주는 마시지 않았다는 뜻이 됩니다.
• 아래 세 가지 값 중 가장 큰 값을 찾아서 넣어줍니다.
  • i-2 번째 포도주를 마시지 않은 경우 : dp[i-2][0]
  • i-2 번째 포도주를 마시고, 연속해서 1잔을 마신 경우 : dp[i-2][1]
  • i-2 번째 포도주를 마시고, 연속해서 2잔을 마신 경우 : dp\[i-2][2]

 

식으로 표현하면 아래와 같습니다.

// 2번째 전 포도주를 마시지 않았을 경우와, 연속해서 1잔 마셨을 경우와, 2잔 마셨을 경우의 최대값을 찾으면 됩니다.
dp[i][1] = Math.max( Math.max(dp[i-2][0], dp[i-2][1]) , dp[i-2][2] ) + arr[i];

 

dp[i][2]에 대해서는 아래와 같습니다.

• 현재 i 번째 포도주를 마셨고, 현재 포도주를 포함해서 연속으로 2잔을 마신 상태입니다.
• 그렇다는 얘기는, i-1 번째 포도주를 무조건 마셨다는 뜻이 됩니다.
• 하지만, i-1 번째는 반드시 연속해서 1잔을 마신 상태이어야 합니다. (*중요)

 

식으로 표현하면 아래와 같습니다.

dp[i][2] = dp[i-1][1] + arr[i];

 

3. 초기값 설정

최대 i-2번째 까지 탐색하기 때문에 dp[2]까지 값을 설정 해주면 됩니다.

• 1 번째 포도주

dp[1][0] = 0;
dp[1][1] = arr[1];
dp[1][2] = 0;

• 2 번째 포도주

dp[2][0] = dp[1][1];
dp[2][1] = arr[2];
dp[2][2] = dp[1][1] + arr[2];

 

---

 

🗝 전체 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bf.readLine());
        int[] arr = new int[N+1];
        int[][] dp = new int[N+1][3];

        for(int i=1; i<=N; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }

        // init
        int MAX = arr[1];
        dp[1][0] = 0;
        dp[1][1] = arr[1];
        dp[1][2] = 0;

        // N이 1인 경우를 대비해 예외처리
        if(N >= 2) {
            dp[2][0] = dp[1][1];
            dp[2][1] = arr[2];
            dp[2][2] = dp[1][1] + arr[2];
            MAX = dp[2][2];
        }

        // dp
        for(int i=3; i<=N; i++) {
            // 현재 포도주를 마시지 않을 경우
            dp[i][0] = Math.max(dp[i-1][1], dp[i-1][2]);
            // 현재 포도주를 마시고, 연속으로 1잔만 마신 경우
            dp[i][1] = Math.max(Math.max(dp[i-2][1], dp[i-2][2]), dp[i-2][0]) + arr[i];
            // 현재 포도주를 마시고, 지금까지 연속해서 2잔 마신 경우
            dp[i][2] = dp[i-1][1] + arr[i];

            // 최댓값을 비교 후 넣어주도록 합니다.
            if(MAX < dp[i][0])  MAX = dp[i][0];
            if(MAX < dp[i][1])  MAX = dp[i][1];
            if(MAX < dp[i][2])  MAX = dp[i][2];
        }

        System.out.print(MAX);
    }
}