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

 

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

2156번: 포도주 시식

dp로 풀 수 있는 문제이다.

다만 여기에는 생각할 것이 조금 많아서 좀 어려운 편이다.

 

이 문제는 포도주를 연속으로 3개 이상은 마시지 않으면서 최대한 많이 마셔야 한다.

이 "연속으로 3개 이상은 불가" 라는 조건이 꽤 까다로운데

이건 (2579 계단 오르기)를 풀어봤으면 쉽게 해결책을 떠올릴 수 있다.

(두 단계 이전의 값을 이용하여 현재 값을 채운다)

 

문제를 풀기 위해 생각을 하다 보면 문제가 하나 생긴다.

dp값이 항상 이전에 있었던 dp값의 최대를 보장하지 않는다는 것이다.

그렇다 보니 이런 문제를 해결해야 점화식을 세우는 것이 가능하다.

 

문제를 해결하기 위해 이전의 dp값 중 최대를 저장하는 변수를 추가로 만들어준다.

이제 문제를 풀기 위해 필요한 준비물은 모두 갖추어졌다.

 

다음과 같이 dp 테이블을 정의하자.

dp[i] : i번째 포도주를 "마셨을 때" 최대로 마신 포도주의 양

 

i번째 포도주를 마시는 법은 두 가지가 있다.

 

1. i-3, i-1, i 번째를 먹는 방법,
2. i-2, i번째를 먹는 방법.

위에서 말한 정보를 토대로 점화식을 세워보면 다음과 같다.

Max_2를 i-2번째까지의 dp값 중 최대,
Max_3을 i-3번째까지의 dp값 중 최대라고 정의하자.
dp[i] = max(Max_2+arr[i], Max_3+arr[i-1]+arr[i])

 

※ 주의사항

위에서 말했듯이 dp[i]의 값은 i번째 포도주를 마신 경우의 최대이므로

i단계에서 최대의 dp값을 보장하지 않는다.

따라서 i단계에서의 최대로 마신 포도주의 양을 구하기 위해서는

적어도 i-3단계부터 i단계까지의 dp값 중 최대를 답으로 해야 한다.

귀찮으니까 그냥 1부터 n까지 중 최대를

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[10100],arr[10100];
int Max_3,Max_2,n;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>arr[i];
    dp[1]=arr[1];
    dp[2]=arr[1]+arr[2];
    for(int i=3; i<=n; i++){
        Max_2 = max(dp[i-2],Max_2);
        Max_3 = max(dp[i-3],Max_3);
        dp[i] = max(Max_2+arr[i],Max_3+arr[i-1]+arr[i]);
    }
    int ans=0;
    for(int i=n-3; i<=n; i++)
        ans = max(ans, dp[i]);
    cout << ans;
    return 0;
}