[백준] 포도주 시식 (2156번 문제)

백준 문제 풀이 - 포도주 시식 (2156 문제)

문제

문제 확인하기

---

풀이

조건부터 확인해보자.

포도주 n잔이 주어진다고 했다.
입력받은 n잔의 포도주를 담은 배열을 wines라는 배열로 초기화하겠다.
첫번째 잔을 1로 표시하기 위해 wines[n+1]로 선언하고 인덱스 1부터 n까지 초기화 하자.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] wines = new int[n + 1];
for (int i = 1; i <= n; i++) wines[i] = Integer.parseInt(br.readLine());

1 <= n <= 10,000이고, 연속 3잔 이상은 마실 수 없다.
n = 1 일 때, wines[1]을 마시는 경우 밖에 없다.
n = 2 일 때, wines[1]과 wines[2]를 마시는 경우밖에 없다.

n >= 3 일 때부터가 문제다.
연속 3잔 이상 마실 수 없으므로 어떤 잔들을 마실 것인지 정해야 한다.

만약, 현재 k번째 잔을 마실지 말지 결정해야 하는 차례라고 하자.
고려해야 하는 경우의 수는 다음과 같다.

• k번째 잔을 마시지 않는 경우
• k-2를 마시지 않고 k-1과 k를 마시는 경우
• k-1을 마시지 않고 k를 마시는 경우

위 경우 중 가장 큰 값을 골라서 선택해야 한다.
이를 그냥 수행할 경우 매번 첫번째부터 k번째 까지 배열을 반복해야 한다.

만약 k번째 잔까지 진행된 내용(k번째까지의 잔들 중에서 선택하여 마신 양)들을 기록할 수 있다면 어떨까?
이들 내용을 기록해두면 매번 배열을 탐색해서 합을 구하지 않아도 된다.

dp 테이블을 사용해서 k번째 잔까지 선택하여 마신 총량을 기록해두면, 이를 이용하여 간단하게 경우의 수를 고려할 수 있다.
dp[k]는 처음부터 현재까지의 잔들 중에서 선택하여 마신 총량의 최대값을 기록한다.
dp[k-1]은 이전(k-1) 잔까지 진행된 내용이다. 현재(k) 잔을 마시지 않는 것으로 해석할 수 있다.
dp[k-2]는 이전전(k-2) 잔까지 진행된 내용이다. 이전(k-1) 잔을 마시지 않은 것으로 해설할 수 있다.
dp[k-3]은 이전전전(k-3) 잔까지 진행된 내용이다. 이전(k-1) 잔과 이전전(k-2) 잔을 마시지 않은 것으로 해석할 수 있다.

위 내용을 토대로 경우의 수를 고려하면 다음과 같다.

• 아래 내용 중 가장 큰 값을 선택하여 dp[k]에 기록한다.
  • k번째 잔을 마시지 않는 경우 : dp[k-1]
  • k-2를 마시지 않고 k-1과 k를 마시는 경우 : dp[k-3] + wines[k-1] + wines[k]
  • k-1을 마시지 않고 k를 마시는 경우 : dp[k-2] + wines[k]

작성한 코드는 다음과 같다.

import java.io.*;

public class Main {
    private static int[] wines;
    private static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        wines = new int[n + 1];
        for (int i = 1; i <= n; i++) wines[i] = Integer.parseInt(br.readLine());

        dp = new int[n + 1];
        dp[1] = wines[1];
        if (n >= 2) dp[2] = wines[1] + wines[2];
        for (int i = 3; i <= n; i++) {
            dp[i] = tripleMax(
                dp[i - 1], 
                dp[i - 2] + wines[i], 
                dp[i - 3] + wines[i - 1] + wines[i]
            );
        }

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

    private static int tripleMax(int a, int b, int c) {
        return Math.max(Math.max(a, b), c);
    }
}