백준 2156 포도주 시식 / C++

문제 : 2156

풀이 point

다이나믹 프로그래밍을 활용하는 문제이다.
가장 최대를 찾아야한다. dp[1] = 첫번째 값, dp[2] = 첫번째 값 + 두번째 값
dp[3]부터는 점화식이 필요하다.

경우의 수는
1. 3번째 전에서 가장 최대값 + 1번째 전 값 + 본인 값
2. 2번째 전에서 가장 최대값 + 본인 값
3. 1번째 전 값 중 가장 최댓값(본인은 선택안하는 경우의 수 두번 건너뛰기가 가능하다.)

풀이 방법

경우의 수 중 세번째가 가장 중요하다.

점화식을 통해 코드를 작성할 수 있다. 입력을 받을 때는 1부터 dp는 0부터 시작하면 좋다.

코드

//백준 2156, 포도주 시식

#include <iostream>
#include <algorithm>

int arr[10'001];
int dp[10'001];

int main (){

    int N;
    std::cin >> N;
    for(int i{1}; i <=N; ++i) std::cin >> arr[i];
    
    //6 10 13 9 8 1

    dp[0] = 0; dp[1] = arr[1]; dp[2] = arr[1] + arr[2];
    for(int i{3}; i<=N; ++i){
        dp[i] = std::max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]);
        dp[i] = std::max(dp[i], dp[i-1]);
    }
    std::cout << dp[N];

    return 0;
}