[BOJ]2156번: 포도주 시식(c++)

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

2156번: 포도주 시식

 

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int MAX = 10000;
int liq[MAX + 1];
int M[MAX + 1];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> liq[i];
    }
    /*
    점화식
        M[i] : i번째 까지 먹은 최대의 포도주 양
 
        M[i] : max(0번연속, 1번연속, 2번연속)
 
        0번연속: i번째 마시지 않음. 
        1번연속: i - 1번째 마시지 않음. i번째 마심.
        2번연속: i - 2번째 마시지 않음. i - 1번째, i번째 마심.
    */
    M[1] = liq[1];
    M[2] = M[1] + liq[2];
    for (int i = 3; i <= n; i++)
    {
        M[i] = max({M[i - 1]
                , M[i - 2] + liq[i]
                , M[i - 3] + liq[i - 1] + liq[i]});
    }
 
    cout << M[n];
 
    return 0;
}

 

 

TIP1

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

문제에서 이렇게 주어졌으므로, 연속성에 초점을 두어야 한다. 

 

 

TIP2

식을 좀더 간단하게 하자.

 

아래는 처음에 풀었던 방식이다. 

D[i][j] : i번째에서 j번 연속해서 마신 최대 포도주

int D[MAX + 1][3] = { 0, };
 
D[1][1] = liq[1];
for (int i = 2; i <= n; i++)
{
    D[i][0] = max({ D[i - 1][0], D[i - 1][1] , D[i - 1][2] });
    D[i][1] = D[i - 1][0] + liq[i];
    D[i][2] = D[i - 1][1] + liq[i];
}
 
cout << max({ D[n][0], D[n][1], D[n][2] });

 

그런데 M[k] : k번째 마신 최대 포도주라고 하면,

D[i][0] = M[i - 1] 
D[i][1] = M[i - 2] + liq[i]
D[i][2] = M[i - 3] + liq[i - 1] + liq[i] 

가 된다.

 

그래서 마지막으로 다음과 같이 더 간결한 코드가 된다.

M[1] = liq[1];
M[2] = M[1] + liq[2];
 
for (int i = 3; i <= n; i++)
{
    M[i] = max({M[i - 1]
            , M[i - 2] + liq[i]
            , M[i - 3] + liq[i - 1] + liq[i]});
}