[알고리즘 문제] 백준2156 - 포도주 시식

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

2156번: 포도주 시식

dp를 사용하는 전형적인 문제인데, 다른분의 풀이를 참고하였습니다. 이런 비슷한 패턴으로 많이 나오는데 익숙해져야 겠습니다.

 

문제는 조건을 만족하면서 포도주를 마셨을 때 가장 많은 마신 포도주 양입니다. 사실 n번쨰 포도주를 마실지 안마실지는 모릅니다. 마시거나, 안마시거나 둘 중 하나겠죠. n번째 포도주를 만났을 때(아직 마시거나, 마시지 않거나 어떤 것도 하지 않음) 우리가 할 수 있는 건3가지 경우 이다.

 

그리고 문제를 푸는데 사용한 배열을 다음과 같이 2개의 배열이다.

dp[n] = n번째 까지 마신 포도주의 최대양

wines[n] = n번째 포도주 양

 

1. n번째 포도주를 마시지 않는다 : dp[n] = dp[n-1]

n번째 포도주를 마시지 않는 다는 것은 dp[n]에 더해지는 포도주 량이 없다는 것을 의미 한다. 그렇기 때문에 이전에 마신 포도주 양(dp[n-1])이 그대로 온다.

 

2. n번째 포도주를 마시고 n-1번째 포도주는 마시지 않는다 : dp[n] = dp[n-2] + wines[n]

그냥 n번째 포도주만 한번 마셔버리는 경우 입니다. 그렇기 때문에 dp[n]에는 dp[n]값을 더해줍니다. 그리고 이저의 최대 포도주량을 더해주어야 하는데, 이 값은 dp[n-2]에 있습니다. n-1은 고려하지 않기 때문이죠.

 

3. n번쨰 포도주를 마시고 n-1번쨰 포도주도 마신다. : dp[n] = dp[n-3] + wines[n] + wines[n-1]

2잔을 연속으로 마시는 경우로 dp[n]에는 wines[n] + wines[n-1]값을 넣어 줍니다. 또한 그전까지 마신 포도주의 량은 dp[n-3]에 저장되어 있을 것입니다. dp[n-3]인 이유는 dp[n-2]를 넣어 버리면 3번 연속 마시는 경우가 되버리기 떄문입니다. 

 

코드에서 1,2,3번의 경우를 나누어서 해도 되지만 그냥 한줄에 작성하였습니다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{

    int dp[10001] = {0};
    int wines[10001] = {0};

    int n;
    cin >> n;

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

    dp[1] = wines[1];

    if (n > 1)
    {
        dp[2] = wines[1] + wines[2];
    }

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

    cout << dp[n];
    return 0;
}