Tech/Problem Solving

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

Bellroute 2020. 3. 5. 17:34

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

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고

www.acmicpc.net

접근 방법

다이나믹 프로그래밍 문제로 이전에 풀었던 백준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]);
    }
}
반응형