[C++] 백준 2156번 : 포도주 시식

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

---

문제 풀이

 이전에 계단 오르기와 비슷한 문제. 차이점은 마지막을 포함하는지 안 하는지이다.

따라서 단순하게 3회 연속만 따지면 된다.

첫 잔에서 최대는 당연히 첫 잔이다.

둘째 잔까지도 두 잔의 합이 최대이다.

세 번째부터 약간 달라지는데 연속 3번이 안되기 때문에 최대는 1번 + 2번 or 1번 + 3번 or 2번 + 3번이다.

배열 DP는 n번째 잔까지의 최댓값을 저장하고 glasses는 n번째 잔의 용량을 저장한다.

 

n번째 잔까지 최댓값인 DP[n]는 DP[n-1], DP[n-2] + glasses[n], DP[n-3] + glasses[n-1] + glasses[n] 중의 최댓값을 저장하면 된다.

DP[n-1] 은 n번째 잔을 마시지 않은 경우.

DP[n-2] + glasses[n] 은 n번째 잔을 마시고 직전 잔을 마시지 않은 경우.

DP[n-3] + glasses[n-1] + glasses[n] 은 n번째 잔과 직전의 잔을 마신 경우이다.

느낀 점

 점화식만 잘 생각할 수 있다면 다소 쉬운 문제이다. 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int glasses[10001] = { 0, };
int dp[10001] = { 0, };

int main() {
	cin >> n;
	for (int i = 1; i <= n;i++) {
		cin >> glasses[i];
	}

	dp[1] = glasses[1];
	dp[2] = glasses[1] + glasses[2];
	for (int i = 3; i <= n;i++) {
		dp[i] = max(dp[i - 1], max(dp[i - 2] + glasses[i], dp[i - 3] + glasses[i - 1] + glasses[i]));
	}

	cout << dp[n];
}