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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

//포도주를 선택하면 다 마시고 원래 위치에 놓는다.
//1~n까지 번호
//n개의 포도주
// 
//연속으로 놓여있는 3잔을 모두 마실 수는 없다.
//가장 많은 양의 포도주를 마셔라.
//1이상 10000이하의 n
//입력
//첫째줄 n개
//둘째줄 n + 1번째까지 포도주의 양 0이상 1000이하

int main() 
{
    int n;
    cin >> n;
    vector<int> grape(n, 0);
    vector<int> dp(n, 0);

    for (int i = 0; i < n; i++)
    {
        cin >> grape[i];
    }

    //dp0 grape0
    //dp1 grape1 + dp0
    //dp2 grape2 + dp0(grape0) or grape2 + grape1 or dp1
    //dp3 grape3 + dp1 or grape3 + grape2 + dp0 or dp2 
    //dp[n] = grape[n] + dp[n-2] or grape[n] + grape[n-1] + dp[n-3] or dp[n-1]

    if (n > 0)
    {
        dp[0] = grape[0];
    }
    if (n > 1)
    {
        dp[1] = grape[1] + dp[0];
    }
    if (n > 2)
    {
        dp[2] = max({ grape[2] + grape[0], grape[2] + grape[1], dp[1] });
    }

    for (int i = 3; i < dp.size(); i++)
    {
        dp[i] = max({ grape[i] + dp[i - 2], grape[i] + grape[i - 1] + dp[i - 3], dp[i - 1] });
    }

    cout << dp[n - 1];

    return 0;
}

 

풀이

1. 모든 경우의 수를 다 따져가며 써본다.

2. 그 경우의 수를 dp적 방식으로 쌓아나가본다.

3. 완성된 점화식을 적는다.

 

느낀점

모든 경우의 수를 따질 때 이해가 안가는 부분이 있다면 그냥 dp는 이럴것이다 생각하고 넘기면 오히려 잘 풀리는 것 같다. 일단 최대한의 규칙을 찾아보는게 좋은 것 같다. 위 문제의 형식은 그래도 많이 나오는 것 같다. n개의 선택과 공백을 이용한 최대한의 값을 구하는 문제를 풀 때는 이런 규칙을 찾아보는 방식으로 많이 따져봐야될 것 같다.

 

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