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

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

( 문제 바로가기 )

( 문제를 다시 푸는 과정에서 보다 상세한 설명을 다시 포스팅 해놓았습니다. 이 글을 읽으셔도 무관하지만, 보다

  구체적인 설명을 원하시는 분들은 아래의 링크를 타고 가시면 됩니다 ! )

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

[ 문제설명 ]

- 포도주의 전체 종류의 갯수와, 그 종류별로 들어있는 양이 입력으로 주어진다.

- 포도주를 연속으로 3잔 마실 수 없을 때, 가장 많이 먹을 수 있는 양을 출력시키면 된다.

[ 문제풀이 ]

1) 포도주의 양을 저장하는 배열 Arr와 최댓값을 저장하는 DP배열을 사용한다.

2) Arr[N] = N번째 포도주의 양을 의미하고, DP[N] = N번째 까지의 마신 포도주의 최대 양을 의미한다.

3) 초기식을 구해보면 DP[1] = Arr[1]이 된다. (배열 0번 사용 안했음 ! ==> DP[0] = Arr[0] = 0)

   DP[2] = Arr[1] + Arr[2]가 된다. (두번째 포도주잔 까지의 최대양 = 당연히 첫번째 포도주의양 + 두번째 포도주의 양)

   DP[3] = ??

   3잔을 연속해서 마실 수 없기 때문에, DP[3] = Arr[1] + Arr[2] + Arr[3]으로 표현할 수가 없다. 이 경우에는 조건에

   위배되기 때문이다. 생각해보면 3번째 잔까지의 포도주의 최대 양은...

   "1번째잔 + 3번째잔" or "2번째잔 + 3번째잔" or "1번째잔 + 2번째 잔" 3개 중 최대양이 된다.

   그럼 N번째 잔을 마실 때 최대양을 생각해보자.

   N번째 잔을 마실 때 최대양은 " N-3번째 잔 까지의 최댓값 + N-1번째 잔 + N번째 잔 " or 

    " N-2번째 잔 까지의 최댓값 + N번째 잔 " or " N-1번째 잔 까지의 최댓값 "

   어떻게 N번째 잔이 존재하는데, N-1번째 잔까지의 최댓값이 최대가 될 수 있을까??? 

   극단적으로 예를 들어보자면, N = 6이고 포도주의 양이 0 1 2 200 200 1 이라고 해보자.

   이 경우, 최댓값은 1+200+200 = 401이 되는데, 이 경우는 N번째 잔을 포함하지 않은 것이다. 그럼 N번째 잔을 포함한다고

   생각해보면, 가장 마지막 1이 포함되어야 하고, 최댓값은 1 + 2+ 200 + 1이 되어서 204 밖에 나오지 않을 것이다.

   따라서, N번째 잔을 꼭 선택해야 하는 문제가 아니기 때문에, N-1번째 까지의 최댓값이 최대가 될 수 있는 것이다.

4) 위의 식을 토대로, 점화식을 세워보면

   DP[i] = DP[i - 3] + Arr[i - 1] + Arr[i] vs DP[i - 2] + Arr[i] vs DP[i - 1] 이 3개의 값 중 최댓값이 된다.

[ 소스코드 ]

 

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 10000 + 1
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    memset(Arr, 0, sizeof(Arr));
    memset(DP, 0, sizeof(DP));
}
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    DP[0] = Arr[0] = 0;
    DP[1] = Arr[1];
    DP[2] = Arr[1] + Arr[2];
    // 3잔 연속 마실 수 없다.
    // 1. 마지막 잔을 기준으로 3번째 앞에 잔을 마시고, 2번째 앞에 잔을 건너뛰고 1번째 앞에 잔 + 마지막잔 
    // 2. 마지막 잔을 기준으로 2번째 앞에 잔을 마시고 + 마지막 잔
    // 3. 마지막 잔을 마시지 않고, 1번째 앞에 잔의 최댓값
    for (int i = 3; i <= N; i++)
    {
        DP[i] = Bigger(DP[i - 3] + Arr[i - 1] + Arr[i], Bigger(DP[i - 2] + Arr[i], DP[i - 1]));
    }
}
 
void Solve()
{
    Initialize();
    Input();
    Solution();
 
    cout << DP[N] << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}