2156_포도주 시식

▶실버1

풀이

연속으로 3잔을 마실 수 없으므로 2잔을 연속으로 마시면 한 잔은 쉬어야 하는데, 최대의 합을 내기 위해서는 연속 두 잔 이상을 마시지 않으면 안된다.

즉, 1번 잔을 마셨으면 꼭 2번 잔을 마시거나 3번 잔을 마셔야 한다. 2번과 3번을 모두 마시지 않으면 최대 값을 낼 수 없다.

이 점을 참고!

 

예제에서 5번째 잔까지만 표로 나타내면

6

10

13

9

8

여기서 모든 경우의 수는

(1, 2, 4, 5)

(2, 3, 5)

(1, 3, 4)

이다.

 

① (1, 2, 4, 5) => dp[2] + arr[4] + arr[5]

② (2, 3, 5) => dp[3] + arr[5]

③ (1, 3, 4) => dp[4]

 

이를 점화식으로 나타내면

dp[i] = max({ dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i], dp[i - 1] })

 

코드

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

int dp[100001];
int arr[100001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		if (i == 1) {
			dp[i] = arr[i];
		}
		else if (i == 1) {
			dp[i] = dp[0] + arr[i];
		}
		else {
			dp[i] = max({ dp[i - 2] + arr[i], dp[i - 3] + arr[i] + arr[i - 1], dp[i - 1]});
		}
	}
	cout << dp[n];
}