#2156번 포도주 시식 (C++)

링크 : www.acmicpc.net/problem/2156

2156번: 포도주 시식

이 문제는 크게 2가지의 조건을 고려하여 최대값을 구해야한다.

 

1. i번째 음료를 마시는 경우

 

빨간색 : 해당값 까지의 합산 최대값 / 파란색 : 해당값

 

(1) i번째 음료 / i-3번째까지의 음료 중 큰 합산 값 / i-1번째 음료

 

 

(2) i번째 음료 / i-2번째까지의 음료중 큰 합산 값

 

2. i번째 음료를 마시지 않은 경우

 

 

(1) 1번에서 최대값과 i번째 직전의 음료와 값을 비교한다.

 

---

 

위의 그림이 이해가 되지 않는다면, 아래 테스트 케이스가 통과되는지 확인해보자.

 

입력값 : 6 100 100 1 1 100 100

출력값 : 400

 

---

#include <iostream>
#include <vector>

using namespace std;

int max(int a, int b) { return a > b ? a : b; }

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n = 0, temp = 0, ans = 0;
	cin >> n;
	vector<int> v;
	int arr[10000] = { 0, };
	for (int i = 0; i < n; i++) {
		cin >> temp;
		v.push_back(temp);
	}
	arr[0] = v[0];
	arr[1] = v[0] + v[1];
	for (int i = 2; i < v.size(); i++) {
		arr[i] = max(arr[i-2], v[i-1]+arr[i-3]) + v[i];
		arr[i] = max(arr[i], arr[i - 1]);
	}
	for (int i = 0; i < v.size(); i++) {
		if (ans < arr[i]) ans = arr[i];
	}
	cout << ans << "\n";
	return 0;
}