[동적계획법 (D.P.)] 백준 2156: 포도주 시식, Java

1. 접근

규칙에 따라서 가능한 계획법을 짜도록 합니다.

동적계획법에 차근차근 저장할 배열과 입력을 받아 포도주 양을 저장할 배열이 필요했습니다.

동적계획법의 배열은 dp, 포도주 양을 저장할 배열은 arr라고 합시다.

 

규칙1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주를 모두 마시고 원래 위치에 다시 놓는다.

규칙2. 연속으로 놓여 있는 3잔을 모두 마실 수 없다.

 

연속으로 3잔을 안 마시기만 하면 됩니다.

차근차근 적어 나가봅니다.

dp[1] = arr[1]

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

 

이제 3잔 째로 갈리게 됩니다.

1번 포도주를 마시고 3번 포도주를 마시는 것과

2번 포도주를 마시고 3번 포도주를 마시는 것 중 더 마시는 것은 무엇인가?

dp[3] = Math.max(dp[1] + arr[3], arr[2] + arr[3])

 

4번 째 잔을 마시게 되면 조건이 하나 더 추가될 수 있습니다.

2번 포도주 까지 마신 것에 더해 4번 포도주를 마시는 것괴

1번 포도주 까지 마신 것에 더해 3번 포도주, 4번 포도주를 마시는 것이 더 마시는 것은 무엇인가?

dp[4] = Math.max(dp[1] + arr[3] + arr[4], dp[2] + arr[4])

 

2. 해결

위의 규칙대로 5, 6 ... 번째 잔은 4번째 잔과 마찬가지로 점화식을 세울 수 있습니다.

즉, dp[n] = Math.max(dp[n - 3] + arr[n - 1] + arr[n], dp[n - 2] + arr[n])

 

하지만 이렇게만 풀었을 때 문제가 발생했습니다.

연속으로 된 포도주이지만 바로 다음이 아닌 안 마시고 건너 뛸 수 있다는 사실이 있었습니다.

그렇게 되면 dp[n] 과 dp[n - 1]의 값을 비교하여 더 큰 것을 저장해야 했습니다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 3];
        int[] dp = new int[n + 3];

        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine()); // 포도주의 양 저장
        }

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

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

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

        br.close();
    }
}