포도주 시식 2156

문제

접근 방법

2번째 규칙에서 DP문제의 기운이 크게 느껴졌다.
연속으로 3잔이라는 것은 2잔을 먹고 1잔을 건너뛰라는 것이다.

6, 10, 13, 9, 8, 1을 순서대로 보자.
6만 있다면 6을 택한다.
6, 10이 있다면 6, 10을 택한다.
6, 10, 13이 있다면 10, 13을 택한다.
6, 10, 13, 9가 있다면 6, 10, 9를 택한다.
가장 큰 수였던 13이 버려진 것이다.

6, 10, 13, 9, 8가 있다면 6, 10, 9, 8을 택한다.
이후 1은 무시당한다.
이를 표로 나타내보자

6	10	13	9	8	1
6	16	23	32	33	33

3개가 되었는지 확인할 방법이 필요하다.

	6	10	13	9	8	1
1	6	10	13	9	8	1

1개만 택한 경우를 설정해둔다.

	6	10	13	9	8	1
1	6	10	19	25	31	29
2	6	16	23	28	33	32

이후 갱신하는데 처음에는 대각선 값+ 위의 값을 하여 2개를 선택한 배열에 갱신해주고 이후 한 칸 건너 왼쪽+ 위를 하여 1개를 선택한 배열에 갱신해준다.

하지만 여기서 멈추면 안 된다.

	10	1	10	1	10
1	10	1	20	12	21
2	10	11	11	21	22

1개만 선택할 때도 한 칸 건너서 가져오는 것이 더 나을 때도 있다.

여기까지 하고 제출했더니 틀렸다.

	10	10	1	1	10	10
1	10	10	11	21	21	22
2	10	20	11	12	31	31

2칸을 버려야 하는 경우도 있기 때문이다.

간단하게 만들어야 한다.

3칸 중 1번째 칸을 버리고 먹는 경우, 1칸을 버리고 먹는 경우, 안 먹는 경우로 나뉘는 것이다.

10	10	1	1	10	10
10	20	20	21	30	40

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> dp(n + 1), wine(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> wine[i];
    dp[0] = wine[0];
    dp[1] = wine[1];
    dp[2] = wine[2] + wine[1];
    for (int i = 3; i <= n; ++i)
    {
        dp[i] = max(max(dp[i - 3] + wine[i - 1] + wine[i], dp[i - 2] + wine[i]), dp[i - 1]);
    }
    cout << dp[n];
}

풀이

좀 더 넓게 보고 풀어야 하는 문제인 것 같다.
3칸이라는 것을 이용해서 점화식을 만들어야 풀린다.