문제

문제 링크

해설

• 이 문제와 많이 유사한 문제입니다.
  • 다만 중요한 차이점이 있는데, 반드시 1칸 or 2칸 움직여야 한다는 제약조건이 없다는 점입니다.
  • 즉, 최적해를 위해서라면 포도주를 2개 이상 생략할 수도 있습니다.

하기 쉬운 실수

• 위에서 언급했듯, 가장 많은 양의 포도주를 마시는 것 == 최대한 많은 포도주를 선택하는 것이라고 오해할 경우, 자신도 모르게 1칸 또는 2칸 움직이는 제약조건을 만들게 될 수 있습니다.
• 따라서, 재귀함수를 만들어서 1칸만 움직이는 경우, 2칸만 움직이는 경우를 계산할 수 있을 것입니다.
• 이 경우, 위에서 언급했던 문제(2579번)와 정답코드가 거의 같아집니다만, 정답을 받을 수는 없습니다.

6
100 100 1 1 100 100

출력: 301
정답: 400

• 반드시 1, 2칸만 움직이는 경우에는 위 반례를 통과할 수 없습니다.

다시 해설로 돌아오겠습니다.

• i번째 포도주를 마셔야 할 때,
  1. i번째 포도주를 마시지 않는 경우
  2. i번째 포도주를 마시는 경우
     1. 2칸 움직인 경우
     2. 1칸 움직인 경우
• 위 경우의 수를 코드로 구현하면 다음과 같습니다.
• DP[n]: 1번 포도주부터 n번 포도주까지 있을 때 마실 수 있는 최대 포도주 량
• DP[n] = max(DP[n - 1], max(DP[n - 2], DP[n - 3] + a[n - 1]) + a[n])
  • DP[n - 1]을 그대로 가져오는 것: n번째 포도주를 마시지 않는 것을 의미.
  • DP[n - 2] + a[n] : 1칸 움직인 뒤 n번째 포도주를 마시는 것을 의미.
  • DP[n - 3] + a[n - 1] + a[n] : 2칸 움직인 뒤 n번째 포도주를 마시는 것을 의미.

코드

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

int N, A[10'001], DP[10'001];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	
	DP[1] = A[1]; DP[2] = A[1] + A[2];
	for (int i = 3; i <= N; ++i)
		DP[i] = max(DP[i - 1], max(DP[i - 2], DP[i - 3] + A[i - 1]) + A[i]);
	cout << DP[N];
}

소스코드 링크

결과