백준 2156(포도주 시식)

하용권 2018. 11. 3. 23:37

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int n;
    int f[100001];
    int dp[100001];
    cin >> n;
    for(int i = 1; i<= n;i++) cin >> f[i];
    dp[1] = f[1];
    dp[2] = f[1]+f[2];
    for(int i = 3; i <=n; i++){
        dp[i]= max(dp[i-2]+f[i],dp[i-3]+f[i-1]+f[i]);
        dp[i] = max(dp[i],dp[i-1]);
    }
    cout << dp[n];
    
}
Colored by Color Scripter
cs

점화식 :

i 번째를 마시지 않은 경우 : dp[i] = dp[i-1]

i 번째를 마시고, 그 전 것도 마신 경우 : dp[i] = dp[i-3]+f[i-1]+f[i]

i 번째를 마시고, 그 다음 것을 마실 경우 :dp[i] = dp[i-2] + f[i]