문제 출처

1. 문제설명

  • 효주가 포도주 시식을 하려고 하는데 두 가지 규칙이 있다.
    • 어떤 잔을 선택하면 전부 마셔야 한다.
    • 연속으로 놓인 3잔을 마실 수 없다.
  • 각 포도주 잔에 양이 주어졌을 때 최대로 많이 마실 수 있는 양을 구하라



2. 알고리즘 설계

  • DP 문제
  • 핵심은 연속으로 놓인 3잔을 마실 수 없다는 것
    • 즉 4개의 잔이 있을 때,
      • 1번째 잔, 3번째 잔, 4번째 잔을 마신 경우
      • 2번째 잔, 4번째 잔을 마신 경우를 비교하면 된다.
  • 주의할 건 N번째 잔의 최대 값을 계산했는데, N-1번째 잔의 값이 클 수 있다.
    • 따라서, N번째 잔 계산 이후 N vs N-1을 해줘야 한다.



3. 로직

  • 점화식
    • DP[i] = max(DP[i - 3] + arr[i - 1] + arr[i], DP[i - 2] + arr[i]);
    • DP[i] = max(DP[i], DP[i-1])



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 100001;
int DP[SZ];
int arr[SZ];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	DP[1] = arr[1];
	DP[2] = DP[1] + arr[2];

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