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

백준의 포도주 시식(2156) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

간단한 예시를 통해서, 포도주를 어떻게 마셨을 때, 가장 최대로 마실 수 있는지 알아보자.

5개의 포도주 잔이 있고, 그 5개의 잔에 들어있는 포도주의 양이 [ 1 , 2 , 3 , 4 , 5 ] 라고 가정해보자.

그럼 이 때, 마실 수 있는 최대양을 구해보자.

우리가 생각해줘야 할 조건은 딱 한가지가 있다. 바로 "연속한 3잔을 모두 마실 수는 없다" 이다.

그럼 지금부터는 포도주를 앞에서 부터 순서대로 마셔볼 건데, 무조건 마시는 상황이 아니라, "x번째 잔 까지 왔을 때, 마실 수 있는 포도주의 최대양" 을 기준으로 생각을 해보자. 즉, 내가 현재, x번째 잔 까지 왔는데, 이 x번째 잔을 무조건 마셨다고 가정하고 최댓값을 구하는 것이 아니라 , x번째 잔 까지 왔을 때의 최댓값을 구해보자. 왜냐하면, x번째 잔 까지 왔을 때, 해당 포도주 잔을 무조건 마시는 경우가 최대가 아니라 마시지 않았을 때 최댓값이 되는 경우도 존재하기 때문이다.

그럼 첫 번째 포도주 잔부터 알아보자. - "첫 번째 잔 까지 왔을 때, 마실 수 있는 포도주의 최대양"

당연히 '1'이다. 왜 ?? 첫 번째 포도주 잔 이전에는 그 어떤 포도주 잔이 없기 때문에, 이전까지 마신 포도주의 최대양은 0이라고 생각할 수 있다. 그렇기 때문에 첫 번째 잔 까지 왔을 때, 마실 수 있는 포도주의 최대양은 무조건 첫 번째 포도주 잔을 마셨을 때 얻을 수 있는 양인 '1'이 된다. 위에서 언급한 조건 따위는 생각하지 않아도 되는 경우이다.

[ 첫 번째 포도주 까지 마실 수 있는 포도주의 최대양 = 1 ]

두 번째 포도주 잔을 알아보자. - "두 번째 잔 까지 왔을 때, 마실 수 있는 포도주의 최대양"

먼저 두 번째 잔 까지 오는 경우를 한번 생각해보자.

1. 첫 번째 잔을 마시고 → 두 번째 잔으로 오는 경우

2. 첫 번째 잔을 마시지 않고 → 두 번째 잔으로 오는 경우

이렇게 2가지 경우가 존재한다. 보다 정확하게 말하자면, 총 4가지 경우가 발생한다. 왜 ? 위의 2가지 경우에는 단순히 "두 번째 잔으로 오는 경우" 라고만 표시를 해두었지, 두 번째 잔을 마시냐 안마시냐에 대해서는 언급하지 않았다. 즉 ! 위의 2가지 경우에서 각 경우마다, 두 번째 잔을 마시는 경우와 마시지 않는 경우가 존재하기 때문에 보다 정확하게 말하자면 총 4가지 경우가 발생하는 것이다. 그런데 ! 과연 두 번째 잔을 계산해야 하는 상황에서 "두 번째 잔을 마시지 않는 경우" 를 생각해주어야 할까 ??? 생각해줄 필요가 없다. 왜 ? 문제에서 제시된 조건인 "연속된 3잔은 모두 마실 수 없다" 에 아무런 영향을 미치지 않기 때문이다. 이 두 번째 잔을 마심으로 인해서, "연속된 3잔을 모두 마시게 되므로 조건에 위배된다" 라는 상황이 발생한다면, 마시는 경우와 마시지 않는 경우를 구분해서 계산을 하겠는데, 기껏 해봤자 이제 두 번째 잔이다. 첫 번째 잔을 마시든 안마시든, 두 번째 잔을 마시든 안마시든 상관없이 절대로 "연속된 3잔은 모두 마실 수 없다" 라는 조건에 위배되지가 않는다. 그래서 위와 같이 적어놓았다.

위의 2가지 경우 모두, 조건에 위배되지 않는다. 즉 ! 위의 2가지 경우 중에서 더 큰 값이 바로 두 번째 잔 까지 왔을 때, 마실 수 있는 포도주의 최대양이 될 것이다.

계산을 해보면 첫 번째 경우는 1 + 2 = 3 이 되고 , 두 번째 경우는 2 가 된다. 따라서, 첫 번째 경우처럼 마셨을 경우, '3'이라는 최대값을 구할 수 있다. 그런데 ! 사실 위에서 말한 2가지 경우 중에, 두 번째 경우는 고려를 해볼 필요도 없다.

왜냐하면 포도주의 양은 1000이하의 음이 아닌 정수이기 때문에, 최소 0이라는 것을 의미한다.

즉 ! 첫 번째 잔을 마시고 두 번째 잔을 마시는 경우가 무.조.건 첫 번째 잔을 마시지 않고 두 번째 잔으로 바로오는 경우보다 크거나 같아진다.

[ 두 번째 포도주 까지 마실 수 있는 포도주의 최대양 = 3 ]

세 번째 포도주 잔을 알아보자. - "세 번째 잔 까지 왔을 때, 마실 수 있는 포도주의 최대양"

세 번째 포도주 잔은 위에서 이야기한 첫 번째 , 두 번째 포도주잔들과는 조금 다른 이야기를 시작해야 한다. 왜 ?? 처음으로 조건을 생각해줘야 하는 포도주 잔이기 때문이다.

먼저, 세 번째 잔 까지 왔을 때 마실 수 있는 경우를 생각해보자. 말로 하나하나 적으면 너무 기니까 간단하게 O , X로만 표시를 해보자. 예를 들어서 O O O 는 첫 번째 잔을 마시고, 두 번째 잔을 마시고, 세 번째 잔을 마시는 경우를 의미한다.

1. O O X

2. O X O

3. X O O

4. X O X

5. X X O

6. O X X

7. X X X

제시된 조건에 위배되지 않고 세 번째 포도주 잔까지 왔을 때 발생할 수 있는 경우의 수는 위와 같이 5가지가 존재한다.

첫 번째 경우 얻을 수 있는 포도주의 양 = 1 + 2 = 3

두 번째 경우 얻을 수 있는 포도주의 양 = 1 + 3 = 4

세 번째 경우 얻을 수 있는 포도주의 양 = 2 + 3 = 5

네 번째 경우 얻을 수 있는 포도주의 양 = 2

다섯 번째 경우 얻을 수 있는 포도주의 양 = 3

여섯 번째 경우 얻을 수 있는 포도주의 양 = 1

일곱 번째 경우 얻을 수 있는 포도주의 양 = 0

위의 값들을 비교해면 세 번째 경우인, X O O 로 마셨을 경우 최대 '5'를 마실 수 있다. 그런데 ! 이렇게 다 비교를 할 수는 없다. 네 번째와 다섯 번째로 가면 갈수록 점점 더 경우의 수가 많아질텐데 이렇게 하나하나 비교를 할 수는 없다.

그래서 위의 경우들에서 딱히 비교해보지 않아도 되는, 공통된 특징을 가지는 놈들끼리 한번 묶어보자.

{ 1 , 4 , 6 , 7 } 번 Case.

본인은 가장 먼저 위의 4가지 Case를 하나로 묶어 보았다. 공통점을 찾아보면, 모두 "세 번째 잔을 마시지 않는 경우" 라는 것이다. 이 Case들은 3번째 잔을 마시지 않기 때문에 어쩌면 문제의 조건에 위배될 상황이 절대로 발생하지 않을 놈들이다.

그리고 1 , 4 , 6 , 7 번 Case들 중에서 최댓값을 찾아보면, 1번 Case인 O O X가 '3'으로 최댓값이 되는데, 이 값은 "두 번째 잔 까지 왔을 때 마실 수 있는 포도주의 최대양"을 의미한다. 즉 ! "내가 현재 x번째 잔까지 왔을 때, x번째 잔을 마시지 않는다고 가정한다면, 이 때 얻을 수 있는 포도주의 최대양은 x - 1번째 포도주잔까지 왔을 때 마실 수 있는 포도주의 최대 양" 이 된다는 것이다.

위의 한 마디 문장으로 , { 1 , 4 , 6 , 7 } 4개의 Case를 하나로 추려내서 계산을 할 수가 있다.

즉 ! 내가 현재 N번째 잔일 때, N번째 잔을 마시지 않는다고 가정할 경우, 마실 수 있는 포도주의 최대양은 N - 1번째 잔까지 왔을 때 마실 수 있는 포도주의 최대양 과 같다 !

그럼 계산하지 않은 { 2 , 3 , 5 } 번 Case들을 보자. 이 Case들은 공통점이 "세 번째 잔을 마시는 경우" 라는 것이다.

이 Case들의 공통점을 한 가지 더 찾아보자면 "세 번째 잔을 마시기 위해서 , 최소 ! 첫 번째 혹은 두 번째 잔 중 하나를 마시면 안된다는 것" 이다.

2번 Case는 O X O 로, 두 번째 포도주 잔을 마시지 않은 경우이다.

3번 Case는 X O O 로, 첫 번째 포도주 잔을 마시지 않은 경우이다.

5번 Case는 X X O 로, 첫 번째, 두 번째 포도주 잔을 모두 마시지 않은 경우이다.

그럼 여기서 우리가 계산하고자 하는 포도주 잔이 세 번째가 아니라 굉장히 큰 숫자라고 한번 가정을 해보자.

그 전에 포도주 잔 중에 어떤 잔을 마셨는지 마시지 않았는지는 모르겠다. 그런데 다음과 같은 상황이라고 가정을 해보자.

? ? ? ? ? ? ? ? ? ? ? ? ? O X O

? ? ? ? ? ? ? ? ? ? ? ? ? X O O

? ? ? ? ? ? ? ? ? ? ? ? ? X X O

위와 같은 상황인 것이다. 위와 같은 상황이더라도, '?'의 상태들이 마셨는지 안마셨는지 구체적으로는 모르지만, 절대로 조건에 위배되는 상황은 발생하지 않는다 라고만 한다면, 위의 상황처럼 포도주를 마실 수 있게 된다.

이 상황에서 가장 마지막에 'O'로 체크된 포도주 잔을 N 번째 잔이라고 가정하고, 위의 3가지 Case들을 계산해보자.

1번 Case = N - 2번째 잔까지 왔을 때, 마실 수 있는 포도주 양의 최댓값 + N번째 포도주의 양

2번 Case = N - 3번째 잔까지 왔을 때, 마실 수 있는 포도주의 양의 최댓값 + N - 1번째 포도주의 양 + N번째 포도주의 양

3번 Case = N - 3번째 잔까지 왔을 때, 마실 수 있는 포도주의 양의 최댓값 + N번째 포도주의 양

이렇게 정리를 할 수가 있다. 그런데 3번 Case를 주목해보자. 최댓값이 될 가능성이 있는 놈일까 ?? 절대로 없는 놈이다. 왜 ?? 2번 Case에서 N - 1번째 포도주의 양 만큼을 안 마시고 버린 경우와 똑같기 때문이다. 포도주의 양의 최솟값은 0이기 때문에 마실 수 있다면 무조건 마시는게 최댓값에 영향을 미칠 것이다. 그런데, 2번 Case 처럼 마실 수도 있는 포도주 잔인데도, 굳이 마시지 않고 버려놓고, 2번 Case보다 큰 값이 발생할 수 있을까 ?? 절대로 그럴 수가 없다. 즉 ! 3번 Case는 비교할 필요가 없다.

그리고 여기서 정리를 해보자. 내가 현재 N번째 잔 까지 왔을 때, N번째 잔을 마신다고 가정했을 때, 마실 수 있는 포도주의 최대양은 'N - 2번째 잔까지 마셨을 때 얻을 수 있는 최대 양 + N번째 잔을 마셨을 때 얻을 수 있는 포도주의 양 ' & 'N - 3번째 잔 까지 마셨을 때 얻을 수 있는 최대 양 + N - 1번째 포도주의 양 + N번째 포도주의 양' 중 더 큰 값이 된다.

그럼 ! a번째 잔 까지 왔을 때, 얻을 수 있는 포도주의 최대양은 b 이다 라는 것을 DP[a] = b 라는 식으로 표현해보자.

DP[1] = Arr[1] 이 될 것이고 , DP[2] = Arr[1] + Arr[2] 가 될 것이다. 이 경우, DP[N]의 값을 구해보면..

DP[N] = Max(DP[N - 3] + Arr[N - 1] + Arr[N] , DP[N - 2] + Arr[N] , DP[N - 1]) 이 된다.

마시지 않는 경우 발생할 수 있는 1가지와, 마시는 경우 발생할 수 있는 2가지 경우, 총 3가지 경우 중 최댓값이 N번째 잔까지 왔을 때, 마실 수 있는 포도주의 최대양이 된다.

이를 다시 돌아와서 4번째 , 5번째 포도주 잔에 적용시켜보자.

DP[4] = ? 위의 식에 그대로 적용시켜보면

DP[4] = Max(DP[1] + Arr[3] + Arr[4] , DP[2] + Arr[4] , DP[3]) 이 된다.

DP[1] + Arr[3] + Arr[4] = 1 + 3 + 4 = 8

DP[2] + Arr[4] = 3 + 4 = 7

DP[3] = 5

즉 ! 최댓값은 8이 된다.

DP[5] = Max(DP[2] + Arr[4] + Arr[5] , DP[3] + Arr[5] , DP[4]) 가 된다.

이런식으로 계산을 해주면 정답을 도출할 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 10010
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    DP[1] = Arr[1];
    DP[2] = DP[1] + Arr[2];
    for (int i = 3; i <= N; i++)
    {
        DP[i] = Max(DP[i - 3] + Arr[i - 1] + Arr[i], DP[i - 2] + Arr[i]);
        DP[i] = Max(DP[i - 1], DP[i]);
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}