[백준] C++ 2156번 : 포도주 시식

풀이과정

---

2579번 : 계단 오르기 (https://yeodo95.tistory.com/21) 와 유사하다.

다른점은 마지막 포도주를 먹지 않아도 된다는 점이다.

 

조건은

1. N-1번째 포도주를 먹고, N번째 포도주를 먹은 경우

2. N-2번째 포도주를 먹고, N번째 포도주를 먹은 경우

3. N-1번째 포도주를 먹고, N번째 포도주를 먹지 않은 경우

 

총 세가지이다

                                                      

따라서 점화식은 d[n] = max( max(d[i-3]+v[i-1]+v[i] , d[i-2] + v[i] ) , d[i-1] ) 이다.

                                                                     1                    2                    3

코드

---

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

int main()
{
	long long d[10001] = { 0, };
	long long iValue[10001] = { 0, };

	int iInput = 0;

	cin >> iInput;

	for (int i = 1; i <= iInput; ++i)
	{
		cin >> iValue[i];
		if(i == 1) d[1] = iValue[1];
		else if(i == 2) d[2] = iValue[2] + d[1];
		else d[i] = max(d[i - 3] + iValue[i - 1] + iValue[i], max(d[i - 2] + iValue[i], d[i - 1]));
	}

	cout << d[iInput] << endl;
	return 0;
}