BOJ - 포도주 시식(2156)

실버1 : 동적계획법 문제이다.

생각

dp[i] : i번째 포도주의 위치에서 마실 수 있는 최대 포도주 양

i번째 포도주의 포도주 양은 세가지 경로에서 답을 찾을 수 있다.

1. dp[i-3] + input[i-1] + input[i]
2. dp[i-2] + input[i]
3. dp[i-1]

Code

//
//  main.cpp
//  test2
//
//  Created by 최완식 on 2021/03/29.
//
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N = 0;
int input[10002];
int dp[10002];
 
int max_value(int a, int b){
    if (a > b) {
        return a;
    }
    return b;
}
 
int main(){
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> input[i];
    }
    
    dp[1] = input[1];
    dp[2] = input[1] + input[2];
    dp[3] = max(max(dp[1] + input[3], input[2] + input[3]), dp[2]);
    
    for (int i = 4; i <= N; i++) {
        dp[i] = max(max(dp[i-3] + input[i-1] + input[i],dp[i-2] + input[i]), dp[i-1]);
    }
    
    cout << dp[N] << endl;
    
    return 0;
}

Reference

• 백준(2156번) - 포도주 시식