[C/C++] 백준 2156번

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

 

안녕하신지..

오늘 풀어볼 문제는 백준 2156번, 실버1 문제이다.

 

두가지 조건을 만족하여 최대한 많은 양의 포도주를 먹는 프로그램을 만들어보자.

 

 

조건

• 포도주는 최대 3잔까지 연속해서 마실 수 없다.
• 이전 두 잔을 마셨다면, 현재 잔은 마실 수 없다.

 

점화식

• dp[i] : i번째 잔까지 마셨을 때의 최대 포도주 양.
• dp[i]=max⁡(dp[i−1], dp[i−2]+wine[i], dp[i−3]+wine[i−1]+wine[i]) :
  • dp[i−1] : 현재 잔을 마시지 않음.
  • dp[i−2]+wine[i]: 한 잔 건너뛰고 현재 잔을 마심.
  • dp[i−3]+wine[i−1]+wine[i]: 이전 잔과 현재 잔을 마심.

 

초기값 설정

• dp[1]=wine[1]
• dp[2]=wine[1]+wine[2]

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N;
    cin >> N;

    vector<int> wine(N, 0);
    vector<int> dp(N, 0);
    for(int i=0; i<N; i++){
        cin >> wine[i];
    }

    dp[0] = wine[0];
    dp[1] = wine[0] + wine[1];

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

    cout << dp[N-1]<<"\n";

    return 0;
}