[백준] 2156번 : 포도주 시식

문제

 

---

풀이

 

myunji.tistory.com/210?category=1154147

[백준] 2579번 : 계단 오르기

이 문제와 유사한 문제이다.

차이가 있다면 계단 오르기 문제에선 마지막 계단을 꼭 밟아야 했지만 여기선 마지막 포도주를 마실 필요가 없단 것이다.

 

위의 두 경우는 i번째 포도주를 마신 경우이고 마지막 경우는 i번째 포도주를 마시지 않은 경우이다.

 

i번째 포도주를 마신 경우

1. i-1번째 포도주를 마시고 i-2번째 포도주는 마시지 않음. i-3번째 포도주에 대한 최댓값

2. i-1번째 포도주를 마시지 않음. i-2번째 포도주에 대한 최댓값

 

i번째 포도주를 마시지 않은 경우

1. i-1번째 포도주에 대한 최댓값

 

이 점화식대로 코드를 작성하면 된다.

---

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

int grape[10001] = {0,};
int dp[10001] = {0,};

int max_grape(int num) {
    for (int i = 1; i <= num; i++) {
        if (i <= 2) { //2개면 그냥 더하면 됨
            for (int j = 1; j <= i; j++)
                dp[i] += grape[j];
        } else //직전 최대 vs 해당+직전+직전직전직전의 최대 vs 해당+직전직전의 최대
            dp[i] = max(dp[i - 1], max(grape[i] + grape[i - 1] + dp[i - 3], grape[i] + dp[i - 2]));
    }
    return dp[num];
}

int main() {
    int n;

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> grape[i];
    cout << max_grape(n) << '\n';
}