백준 2156번 포도주 시식

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

처음 문제를 접했을 땐, 월요일(20일)에 풀었던 계단 오르기와 동일한 규칙인 것으로 생각했었다.

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

하지만, 문제의 조건 중에 '선택하면' 이란 단어를 보고 다른 문제라는 것을 알게되었다.  왜냐하면 계단오르기는 n 번째 계단을 무조건 밟는 것이기 때문에, dp 배열마다 n번째 계단의 값을 더하였기 때문이다.

for(int n = 2 ; n <= num; ++n) {    dp[n][0] = stair[n] + dp[n-1][1];    dp[n][1] = stair[n] + max(dp[n-2][0], dp[n-2][1]); } 출처: http://dokrsky.tistory.com/2 [IT]

이번 문제는 포도주를 선택할 수도, 선택하지 않을 수도 있기 때문에 위의 파란 색 글씨처럼 n번째 포도주의 값을 무조건 더하면 안된다.

즉, 연속으로 놓여있는 3잔을 모두 마실 수 없다. 조건은 

계단오르기 (연속된 세 개의 계단을 모두 밟아서는 안된다.)와 

동일하지만 포도주 선택, 미선택 여부가 추가 되었기 때문에 

dp[n][m] : n번째 포도주를 m 번째로 연속으로 먹었을 때의 최대값으로 설정하였으며, 배열의 column을 3으로 설정하였다.

dp[n][0] : n번째 포도주를 선택하지 않았을 때

dp[n][1] : n-1 단계에서 -> n번째 포도주 시식 여부

dp[n][2] : n-2 단계에서 -> n번재 포도주 시식 여부로 설정하였다.

각 column 별로 확인하면,

dp[n][0] 은 n번째 포도주를 선택하지 않았으므로, n-1번째 포도주 dp 값들 중 가장 큰 값을 고르면 된다. 

dp[n][1] 은 n-1단계에서, n 번째 포도주로 넘어온 경우이므로

1. n-1번째를 먹지않고, n번째를 먹거나

2. n-3번째에서 n-1번째로 넘어온 뒤, n번째로 넘어온 경우

2가지 경우 중에서 최대값과 n번째 와인 값을 더하면 된다.

dp[n][2] 는 n-2 단계에서 n번째 포도주를 시식하러 온 경우 이므로,

n-2단계에서 최대값을 고른 뒤, n번째 와인 값을 더하면 된다.

이후, 최종 값은 column 3개 중 최대값을 고르면 된다. 

#include <iostream>
#include <cmath>
using namespace std;
int main()
{   
    int dp[10001][3] = {0, };
    int n, wine[10001] = {0, };
    int result = 0;
    cin >> n;
    
    for (int i = 1 ; i <= n ; ++i) {
        cin >> wine[i];
    }
    
    dp[1][0] = 0;       // n번째 포도주를 마시지 않았을 때
    dp[1][1] = wine[1]; // n번째 포도주를 1번 연속으로 마셨을 때
    dp[1][2] = wine[1]; // n번째 포도주를 2번 연속으로 마셨을 때
    
    for (int i = 2 ; i <= n ; ++i) {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]);
        dp[i][0] = max(dp[i-1][2], dp[i][0]);
        
        dp[i][1] = wine[i] + max(dp[i-1][0], dp[i-1][2]);
        
        dp[i][2] = max(dp[i-2][0], dp[i-2][1]);
        dp[i][2] = wine[i] + max(dp[i-2][2], dp[i][2]);
    }
    
    result = wine[1];
    for (int i = 1 ; i <= n ; ++i) {
        result = max(dp[i][0], dp[i][1]);
        result = max(result, dp[i][2]);
    }
    
    cout << result << endl;
    
   return 0;
}