문제

이해

N개의 잔에 서로 다른 양의 포도주가 담겨 있다. 효주는 최대한 많은 포도주를 마실려고 한다.

포도주를 마시는 규칙은 다음과 같다.
1. 선택한 잔에 담긴 포도주는 모두 마셔야 하고 제자리에 놓는다.
2. 붙어있는 세 잔의 포도주는 마실 수 없다.

마실 수 있는 포도주의 최대 양을 구한다.

접근

이 문제도 다이나믹 프로그래밍으로 풀 수 있다. 잔을 선택하는 기준이 이전에 선택되었던 잔들에 영향을 받기 때문이다.

예시처럼, 6 - 10 - 13 - 9 - 8 - 1 의 잔이 있을 때 최대로 마시는 경우는
6 + 10 + 9 + 8 = 33 이다. 셋째 잔과 여섯째 잔은 규칙에 의해 마실 수 없다.

규칙에 유의하여 점화식을 작성해보자. i번째 잔에서 마실 수 있는 최대의 값 dp[i]는 우선 크게 두 가지 경우로 나뉜다.

1. 마시지 않는다.
2. 마신다.

1번의 경우를 보자. i번째 잔을 마시지 않으면 i-1번째 잔은 마시던 안마시던 상관없다. 최댓값을 구하기 위해서는 i-1번째에서의 최댓값만 알면 된다. 따라서, dp[i-1]이 된다.

2번의 경우를 보자. i번째 잔에서 마시는 경우, i-1번째에서는 두 가지 분기로 나뉜다.

2-1. i-1에서 마시지 않는다.
2-2. i-1에서 마신다.

2-1번의 경우에서는 i-1에서 마시지 않기 때문에 i-2에서 마시던 안마시던 상관없이 최댓값을 가져오면 된다. 따라서, dp[i-2] + arr[i] 가 된다.

2-2번의 경우에서는 i-1에서 마시기 때문에 규칙 2에 의해서 i-2에서는 마실 수 없다. 따라서, i-3에서의 최댓값을 알면 된다. dp[i-3] + arr[i-1] + arr[i]

이상으로 dp[i]의 총 3가지 점화식을 세울 수 있다.
1. dp[i-1]
2. dp[i-2] + arr[i]
3. dp[i-3] + arr[i-1] + arr[i]

dp[i]는 이 중에서 최댓값을 선택하면 된다.

점화식을 세웠기 때문에 bottom-up, top-down 둘 중 편하게 선택해서 작성하면 된다.

물론, i < 3 범위에서의 dp[i]는 직접 초기화해주어야 한다.

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

코드

bottom-up 방식으로 풀이하였다. 메모이제이션 활용

package java_baekjoon;

import java.util.*;

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

        int N = sc.nextInt();

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

        int[] dp = new int[N + 1];
        dp[1] = arr[1];

        if (N > 1) {
            dp[2] = arr[1] + arr[2];
        }

        for (int i = 3; i <= N; i++) {
            int caseA = dp[i - 2] + arr[i];
            int caseB = dp[i - 3] + arr[i - 1] + arr[i];
            int caseC = dp[i - 1];

            dp[i] = Math.max(caseC, Math.max(caseA, caseB));
        }

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

N이 1일수도 있기 때문에 예외처리를 해주어야 한다. dp[2]가 존재하지 않을 수도 있기 때문에.

결과