[백준 2156] 포도주 시식 (Java)

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

2156번: 포도주 시식

접근 방법

다이나믹 프로그래밍 문제로 이전에 풀었던 백준2579 계단 오르기와 유사해서 비슷하게 접근하였다.

DP[n]이 n번째 포도주를 시식했을 때 최댓값이라고 할 때, 위 그림과 같이 두 가지 경우 중 최댓값을 선택하게 한다.

따라서 위와 같은 점화식을 도출할 수 있다.

 

하지만, 여기서 함정을 조심해야한다.

포도주를 한 번만 건너뛰라는 법이 없다는 것이다. 다시 말해 두번 연속 포도주를 마시지 않는 경우도 고려해야한다.

 

n번째 포도주를 마시지 않았다는 것은 n-1번째 포도주까지는 마셨다는 것으로 볼 수 있다.

따라서, Max(dp[n], dp[n -1]) 의 결과를 dp[n]에 담아야한다.

 

 

소스 코드

import java.util.Scanner;

public class Main {
    private static int n;
    private static int[] numbers;

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

        n = scanner.nextInt();
        numbers = new int[n + 1];

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

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

        dp[1] = numbers[1];

        if (n > 1) {
            dp[2] = dp[1] + numbers[2];

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

        }


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