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

문제

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

2156번: 포도주 시식

문제풀이

 

OXXOO

  OXOO

  OXXO

    OXO

포도주는 3번 연속 마실수 없다, 경우의 수에서 3번 연속 안 마시고 최댓값을 낼 수 없다.

따라서 N번째를 마신다고 가정했을 때

DP[N] = DP[i-4] + Arr[i-1] or

            DP[i-3] + Arr[i-1] or

            DP[i-3] or

            DP[i-2]

중 최대값에 Arr[N]값을 더한 값이다.

DP[N]은 N번째를 무조건 마신다고 가정하였으므로 N을 마시지 않고 N-1, N-2를 마신 경우가 더 클 수 있기 때문에

1부터 N까지 반복하면서 최댓값을 찾아 출력한다.

 

코드

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

int main() {
	int n = 0;
	int i = 0;
	cin >> n;
	vector<int>DP(n + 4, 0);
	vector<int>Arr(n + 4, 0);

	for (i = 4; i < n + 4; ++i) {
		cin >> Arr[i];
	}

	for (i = 4; i < n + 4; ++i) {
		DP[i] = DP[i - 2];
		DP[i] = max(DP[i], DP[i - 3]);
		DP[i] = max(DP[i], DP[i - 3] + Arr[i - 1]);
		DP[i] = max(DP[i], DP[i - 4] + Arr[i - 1]);
		DP[i] += Arr[i];
	}
	int answer = 0;
	for (i = 4; i < n + 4; ++i)
		answer = max(answer, DP[i]);
	cout << answer;
}