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

 

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

 

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

2156번: 포도주 시식

 

---

 

 

해결전략

 

Dynamic Programming (DP) 동적 계획법

---

 

코드 - 방법1

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> v;
vector<int> dp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    v.resize(n+2);
    dp.resize(n+2);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    dp[1] = v[1];
    dp[2] = v[1] + v[2];
    dp[3] = max(max(v[1] + v[3], v[2] + v[3]), v[1] + v[2]);

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

    cout << dp[n];

    return 0;
}

 

 

---

 

코드 - 방법2

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> v;
vector<vector<int>> dp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    v.resize(n+2);
    dp.resize(n+2, vector<int>(4));
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    dp[1][1] = v[1];
    dp[2][0] = v[1];
    dp[2][1] = v[2];
    dp[2][2] = v[1] + v[2];

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

    int answer = max(dp[n][0], max(dp[n][1], dp[n][2]));
    cout << answer;

    return 0;
}

 

 

 

---