포도주 시식 (feat. 백준, 2156번)

포도주 시식
https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2156
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, arr[10001], dp[10001] = { 0 };
	cin >> N;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i];
	dp[1] = arr[1], dp[2] = arr[1] + arr[2];
	for (register int i = 3, x1, x2; i <= N; ++i) {
		x1 = max(dp[i - 2], dp[i - 3] + arr[i - 1]) + arr[i];			// 현재의 잔을 마시는 경우
		x2 = max(dp[i - 1], dp[i - 2] + arr[i]);						// 현재의 잔을 마시지 않는 경우
		dp[i] = max(x1, x2);
	}
	cout << *max_element(dp + 1, dp + N + 1) << endl;
	return 0;
}
// *&)*@*

이 문제는 이전 "계단 오르기" 문제와 유사합니다. 시간이 되신다면 한번 풀어보시길 권장합니다.

계단 오르기 (feat. 백준, 2579번)

1. 위 문제와 차이점은 하나가 있는데, 현재 위치의 값을 더해줄것이냐 안할것이냐 입니다.
2. 계단 오르기는 마지막 도착 계단을 반드시 밟아야 한다 는 조건으로 인해 현재의 위치를 더해주었지만, 포도주 시식은 그렇지 않습니다.
3. 2번과 3번잔을 마시면 4번잔을 마실수 없습니다. 1번과 2번잔을 마시면 다음은 4번잔을 마셔야 합니다. 때문에 현재 잔을 Bi 라고 하고 현재 잔까지 마신 총합을 Ai 라고 한다면, 이는 Ai = max(Ai-2, Ai-3 + Bi-1) + Bi 로 수식을 만들 수 있습니다.
4. 하지만 위 수식은 현재의 잔을 마신다는 가정에서의 수식이므로, 현재의 잔을 마시지 않는다는 가정이라면 위 수식에서 i + 1씩으로만 취하면 됩니다. (Ai = max(Ai-1, Ai-2 + Bi) 입니다. 즉 현재의 잔을 건너띄고 다음잔을 마시게 되는 경우라고 봐도 됩니다.)