백준 2156 포도주 시식

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 포도주가 일렬로 놓여있을 때 가장 많은 포도주를 마실 수 있는 양을 구하는 문제입니다.

 

이때 연속으로 세잔의 포도주를 마실 수 없다는 조건이 있습니다. 따라서 i번째의 잔까지 왔을 때 가장 많은 포도주의 양을 구하기 위해서는

 

총 세가지 경우중 최대값을 찾아야 합니다.

 

1. i번째 포도주를 먹지 않는경우 -> dp[i-1]

2. i-1번째 포도주를 먹지 않고 i번째 포도주를 먹는 경우 -> dp[i-2] + grape[i]

3. i-1번째 포도주와 i번째 포도주를 먹는 경우 -> dp[i-3] + grape[i-1] + grape[i]

세가지의 식이 존재하고 이 세가지 중 가장 max값이 dp[i]가 됩니다.

 

 

#include <iostream>

using namespace std;

/*
	총 세가지의 경우 비교
	1. i번째 포도주를 먹지 않는경우 
	2. i-1번째 포도주를 먹지 않고  i번째 포도주를 먹는 경우 
	3. i-1번째 포도주와 i번째 포도주를 먹는 경우 
*/
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin >> n;
	int grape[10001];
	int dp[10001] = {0, };  
	for(int i = 0; i < n; i++)
		cin >> grape[i];
	
	dp[0] = grape[0];
	if(n == 1) {
		cout<<dp[0];
		return 0;
	}
	if(n >= 2)
		dp[1] = grape[0] + grape[1];
	if(n >= 3)
		dp[2] = max(max(dp[1], grape[0] + grape[2]) , grape[1] + grape[2]);
	
	for(int i = 3; i < n; i++) {
		dp[i] = max(max(dp[i-1], dp[i-2] + grape[i]), dp[i-3] + grape[i-1] + grape[i]);

	}

	cout<< dp[n-1];

	return 0;
}