[2156] 포도주 시식

---

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

2156번: 포도주 시식

 

이 문제는 2579번 계단 오르기 문제와 굉장히 흡사하다.

https://kmyobin.tistory.com/81

[2579] 계단 오르기

 

조건은 2가지이다.

1. 3잔을 연속해서 마실 수 없다.

2. 마신 후 원래 위치에 되돌려 놓는다.

 

 

계단 오르기와 굉장히 유사하지만 다른 점이 있다. 

시작 점과 끝나는 점이 정해져있지 않다는 것.

 

 

그러므로 항상 i번째를 포함시켜 계산했던 2579번과는 달리, i번째에 있는 값을 선택하지 않는 조건도 넣어줘야 한다.

기존(계단 오르기)의 조건

DP[i] = A[i] + A[i - 1] + DP[i - 3];
DP[i] = A[i] + DP[i - 2];

새롭게 추가된 조건

DP[i] = DP[i - 1];

 

 

전체 코드는 아래와 같다.

#include <iostream>
#include <cmath>
using namespace std;

int N;
int A[10000]; int DP[10000];

// DP[i] : i번째에서의 포도주 최댓값
// 현재 포도주를 선택하지 않는 조건도 생각해야함

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

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}

	DP[0] = A[0];
	DP[1] = A[0] + A[1];
	DP[2] = max(DP[1], max(A[0] + A[2], A[1] + A[2])); // 2번째를 선택하지 않는 조건(DP[1])도 생각

	for (int i = 3; i < N; i++) {
		int d1, d2,d3;
		// i번째에 있는 걸 선택 o
		d1 = A[i] + A[i - 1] + DP[i - 3];
		d2 = A[i] + DP[i - 2];

		// i번째에 있는 걸 선택 x
		d3 = DP[i - 1];
		DP[i] = max(d3, max(d1, d2));
	}

	cout << DP[N - 1];
}