[Java] 백준 BOJ / 2156번: 포도주 시식

포도주 시식

문제

---

문제 설명

포도주의 순서와 양이 주어졌을 때, 연속으로 3잔을 마실 수 없다는 조건 하에 가장 많은 포도주를 먹었을 때를 구하는 문제이다.

최근 DP 문제를 풀었다면 계단오르기 문제와 비슷하다고 생각하겠지만 조건이 조금은 다르다.

일단 DP 배열을 2차원으로 생각했는데 그 이유는 내가 n번째 포도주를 골랐을 때의 상태에서 몇잔째 연속으로 마시고있는지를 기준으로 생각했기 때문이다.

그렇게 완성된 생각으로 점화식을 세워봤다.

dp[0][i]

i번째 포도주를 먹지 않을 경우이다.

i번째 포도주를 먹지 않았을 경우에서는 아래 두가지 값 중 큰 값을 찾으면 된다.

• i-1 번째 포도주를 먹었을 때 1잔이였을 경우 : dp[1][i - 1]
• i-1 번째 포도주를 먹었을 때 2잔이였을 경우 : dp[2][i - 1]

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

dp[1][i]

i번째 포도주를 첫잔째로 먹는 경우이다.
그 말은 전 포도주인 i-1 번째 포도주는 먹지 않았다는 말이고 따라서 i-2번째 포도주의 상태를 가져와야 한다.

• i - 2 번째 포도주를 마시지 않은 경우 : dp[i - 2][0]
• i - 2 번째 포도주를 먹었을 때 1잔이였을 경우 : dp[i - 2][1]
• i - 2 번째 포도주를 먹었을 때 2잔이였을 경우 : dp[i - 2][2]

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

dp[2][i]

i번째 포도주를 두잔째로 먹는 경우이다.
당연히 i - 1번째 포도주를 먹었을 경우밖에 없다.

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

초기값 설정

현재 dp의 탐색 범위는 i - 2 까지이기 때문에 dp[2]까지 초기화 해주면 되고 코드는 아래와 같다.

---

코드

import java.util.Scanner;

public class Main_2156 {
    static int n;
    static int[] arr;
    static int[][] dp;
    static int max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        arr = new int[n + 1];
        dp = new int[3][n + 1];

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

        max = arr[1];

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

        if (n >= 2) {
            dp[0][2] = dp[1][1];
            dp[1][2] = arr[2];
            dp[2][2] = dp[1][1] + arr[2];
            max = dp[2][2];
        }


        for (int i = 3; i <= n; i++) {
            dp[0][i] = Math.max(dp[1][i - 1], dp[2][i - 1]);
            dp[1][i] = Math.max(dp[0][i - 2], Math.max(dp[1][i - 2], dp[2][i - 2])) + arr[i];
            dp[2][i] = dp[1][i - 1] + arr[i];
        }

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j <= n; j++) {
                System.out.print(dp[i][j] + " ");
                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
            }
            System.out.println();
        }
        System.out.println(max);
    }
}

---

정리

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

이 부분에서 괄호개수를 헷갈려서 한참 헤맸다.. 괄호를 잘 보고 풀어야한다.