[C++] 백준 2156 - 포도주 시식

0. 주어진 문제

포도주 시식 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	33335	11934	8531	34.344%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 

6
6
10
13
9
8
1

예제 출력 1 

33

1. 풀이

이번 문제는 이전의 계단 오르기(문제, 풀이)를 참고하여 만들었다.

이전 문제와 다른 점은, 다음 단계로 넘어갈 때, 마시지 않는 선택을 할 수도 있는 것이였다.

마시지 않는 선택이 없는 경우의 예시 입력을 넣어준 최대값의 배열인데, 보면 5번째보다 6번째의 값이 작은 것을 볼 수 있다.

이렇게 된 원인은 점화식이 2단계 이전의 배열들과 자신을 더해주는 형식을 취하게 되는데, 막상 바로 이전 배열과는 비교를 하지 않기 때문이다.

바로 이전 배열과 자신의 비교를 통해, 자신이 더 작은 경우, 이번에 술을 마시지 않고, 이전의 배열을 취하는 형태를 택하는 것을 추가적으로 소스에 넣어주니 문제를 해결해 낼 수 있었다.

반례는 더 좋은 글이 있었는데, 더 자세히 궁금한 사람은 밑의 링크를 참조해주시길 바란다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include<iostream>   using namespace std;   int value[10001]; int max_drink[10001];   int Max(int a, int b) {     return a > b ? a : b; }   void calc(int N) {     //초기값     max_drink[1] = value[1];     max_drink[2] = Max(value[2], max_drink[1] + value[2]);     for (int i = 3; i <= N; i++) {         //이전 계단 오르기와 같은 점화식         max_drink[i] = Max(max_drink[i - 2] + value[i], max_drink[i - 3] + value[i - 1] + value[i]);         //추가적으로, 마시지 않는 선택도 존재한다.         max_drink[i] = Max(max_drink[i - 1], max_drink[i]);     } }   int main() {     int N;     cin >> N;     for (int i = 1; i <= N; i++) {         cin >> value[i];     }       calc(N);          cout << max_drink[N] << endl; } Colored by Color Scripter

cs

3. 문제 출처

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

4. 참고

https://mygumi.tistory.com/98(반례 참고하였습니다.)