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

2156번: 포도주 시식

# 문제

 

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

 

# 입력

 

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

 

# 출력

 

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

 

# 예시 입력

6
6
10
13
9
8
1

# 예시 출력

33

---

동적 프로그래밍 문제이다. 이전에 풀었던 계단 오르기(?) 문제였나 그거랑 매우 흡사하다.

2021/01/14 - [Programming/백준] - [백준] 2579번 : 계단 오르기

[백준] 2579번 : 계단 오르기

그래서 너무 쉽네 하면서 계단 오르기 문제와 99% 일치하게 풀었더니 계속 틀리다는 것 이다. 아니 대체 문제가 어디가 다른거지 하면서 열이 오르던 중,,, 하나의 반례를 보게 되었다.

6
1000
1000
1
1
1000
1000

위의 입력을 넣었을 때 최대 값은 4000이 나와야 한다. 그런데 계단 오르기 때의 알고리즘을 그대로 적용하면 3001이 나온다. 이 두 문제의 차이점은..

 

1) 계단은 맨 마지막 계단은 반드시 밟아야 한다. 하지만 포도주 문제는 그렇지 않다.

2) 포도주 문제는 i번 째에 놓여진 포도주를 마시지 않고 다음, 다다음, 다다다음 잔을 마시는 것도 가능하다.

 

알고리즘은 아주 살짝만 변경하면 된다.

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

for i=4 -> x then
	arr[i] -> Math.max(arr[i-4], arr[i-3]) + wine[i] + wine[i-1];
	arr[i] -> Math.max(arr[i-2] + wine[i], arr[i]);

그리고 이 문제는 arr[x](배열의 가장 마지막 인덱스 값)을 구하는 문제일 수도, 아닐 수도 있다. 왜냐면 먹을 가치가 없다고 생각되면 마지막 잔과 그 주변 잔은 마시지 않을 수도 있기 때문이다. 그냥 맘편하게 배열에서 최대 값을 반환받는 메소드를 사용하도록 한다.

 

# Whole Code </> - Java 11

public class Main {

    static int[] wine = new int[10001];

    static long getAnswer(int x){

        long[] arr = new long[10001];
        long max = 0;

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

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

/*
        Arrays.stream(arr).forEach(a -> {
            if(a != 0)
                System.out.println(a);
        });
*/        

        OptionalLong a = Arrays.stream(arr).max();
        if(!a.isPresent()) return 0;
        max = a.getAsLong();
        return max;
    }
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        if(x < 1 || x > 10000) System.exit(0);

        for(int i=1; i<=x; i++){
            wine[i] = sc.nextInt();
            if(wine[i] < 0 || wine[i] > 1000) System.exit(0);
        }

        System.out.printf("%d\n", getAnswer(x));
        sc.close();
    }
}