[백준/C,C++] 2156번: 포도주 시식

www.acmicpc.net/problem/2156

2156번: 포도주 시식

hackids.tistory.com/23

[백준/C,C++] 2579번: 계단 오르기

2579번: 계단 오르기와 되게 유사한 문제입니다. 6잔의 포도주 양이 6, 10, 13, 9, 8, 1과 같을 때를 생각해보겠습니다.

	1번(6)	2번(10)	3번(13)	4번(9)	5번(8)	6번(1)
1잔 연속	6	10	19	25	31	29
2잔 연속		16	23	28	33	32

포도주를 1잔 연속해서 마신 경우 2잔 연속해서 마신 경우가 있습니다. 2잔 연속해서 마신 경우는 이전에 마신 포도주의 값 중 1잔 연속해서 마신 값과 현재 값을 더해주면 될 테고, 1잔 연속해서 마신 경우는 2번 전에 마셨던 포도주의 값 중 큰 값을 현재 값과 더해주면 됩니다. 예제 입력에서 가장 많이 마실 수 있는 포도주의 양은 33이죠. 그런데 여기에는 반례가 존재합니다. 포도주의 양이 100, 100, 1, 1, 100, 100과 같이 존재할 때인데, 이때 포도주를 가장 많이 마시는 방법은 1, 2, 5, 6번째 포도주를 마시고 400 양만큼 마시는 것입니다. 그러면 포도주를 2번 동안 안 먹게 되죠. 3번 마시지 않는 방법은 고려하지 않아도 됩니다. 3번 중 중간에 한번을 무조건 마시는 게 최대량이 나오기 때문이죠.

	1번(100)	2번(100)	3번(1)	4번(1)	5번(100)	6번(100)
1잔 연속	100	100	101	201	300	301
2잔 연속		200	101	102	301	400

즉 n번째 잔에서 1잔 연속 마시는 값은 n - 1, n - 2번째 잔에서 가장 큰 값을 가져와 n번째 잔의 값과 더해주는 것이고, 2잔 연속 마시는 값은 n - 1번째 잔에서 1잔 연속 마신 값과 n번째 잔의 값과 더해주는 것입니다.

#include<iostream>

using namespace std;

#define MAX 10001

int DP[MAX][3];

int main(void)
{
    int n; cin >> n;

    for (int i = 1; i <= n; i++) {
        int temp; cin >> temp;
        if (i == 1) DP[i][1] = temp;
        else {
            int one = max(DP[i - 2][1], DP[i - 2][2]);
            int two = max(DP[i - 3][1], DP[i - 3][2]);
            DP[i][1] = max(one, two) + temp;
            DP[i][2] = DP[i - 1][1] + temp;
        }
    }

    int case1 = max(DP[n][1], max(DP[n][2], DP[n][3]));
    int case2 = max(DP[n - 1][1], max(DP[n - 1][2], DP[n - 1][3]));
    cout << max(case1, case2);

    return 0;
}

최댓값은 마지막 잔과 마지막 이전 잔 중 가장 큰 값을 출력해주면 됩니다. 마지막 이전 잔이 2잔 연속 마신 경우 마지막 잔을 못 마실 수 있기 때문입니다.