백준BOJ 2156 포도주 시식

https://github.com/o920/baekjoon/blob/master/2156.cpp

o920/baekjoon

전에 풀었던 계단문제랑 너무 똑같아서 똑같이 품

 

다른 점은 계단 문제에는 연속 두번 건너뛸 수 없다는 거고

이번에는 연속 두번 건너뛸 수가 있음

그래서 한가지 경우의 수를 더 추가해주면 됨

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10003] = { 0, };
int q[10003];
int main() {
	int n;
	cin >> n;
	for (int i = 3; i < n+3; i++)cin >> q[i];
	for (int i = 3; i < n + 3; i++) {
		dp[i] = max(dp[i-1], q[i] + max(q[i - 1] + dp[i - 3], dp[i - 2]));
	}

	cout << dp[n+2] << endl;
}