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

백준 '포도주 시식' 문제 보러가기

전형적인 DP 문제이다.

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin>> n;
    int arr[n+1], DP[3][n];
    for(int i=1;i<=n;i++){
        cin >> arr[i];
    }
    DP[0][0]=0; DP[1][0] = 0; DP[2][0]=0;
    for(int i=1;i<=n;i++){
        DP[0][i] = max(DP[0][i-1],max(DP[1][i-1],DP[2][i-1]));
        DP[1][i] = DP[0][i-1]+arr[i];
        DP[2][i] = DP[1][i-1]+arr[i];
    }
    cout << max(DP[0][n], max(DP[1][n],DP[2][n]));
}

DP는 연속해서 마신 잔 수를 가리키는 3개의 행(0잔, 1잔, 2잔)과 포도주 잔의 번호를 가리키는 열(1번 ~ n번)로 구성되어있다. 이전 값을 기준으로 더하기를 해줘야하므로 기초가 되는 0번째 열은 모두 0으로 초기화를 해주어야한다.

​

• DP[0][i] : i번째 잔을 지나는 시점에서 연속해서 마신 포도주 잔의 수가 0잔

위의 경우가 가능해지는 경우의 수는 아래와 같다.

1. i-1번째까지 연속해서 한 잔도 마시지 않다가 이번에도 마시지 않기로 선택

2. i-1번째까지는 연속해서 한 잔을 마셨다가 이번에는 마시지 않기로 선택

3. i-1번째까지는 연속해서 두 잔 째 마셨다가 이번에는 마시지 않기로 선택

​

이 중에서 최대값을 골라서 저장한다.

​

• DP[1][i] : i번째 잔을 지나는 시점에서 연속해서 마신 포도주 잔의 수가 1잔

이에 해당하는 경우는 이전에는 포도주를 마시지 않았다가 i번째가 되어서 포도주가 먹는 경우 밖에 없다.

i-1번째에 포도주를 1잔 마셨다면 i번째에는 연속해서 마신 포도주 잔의 수가 2잔이 되고, i-1번째가 연속해서 포도주 2잔을 마신 시점이라면 이번 차례에서는 포도주를 마실 수가 없기 때문이다.

​

• DP[2][i] : i번째 잔을 지나는 시점에서 연속해서 마신 포도주 잔의 수가 2잔

위와 같은 이유로 이에 해당하는 경우는 i-1번째에 연속해서 마신 포도주의 잔이 1잔인 경우밖에 없다.

​

결과는 n번째 포도주 잔을 지났을 때 연속해서 마신 포도주의 잔이 0잔일 때와 1잔일 때, 2잔일 때를 비교해서 가장 큰 것을 출력하면 된다.