2156 포도주 시식

 

풀이코드

#include <iostream>
#include <cstdio>
using namespace std;
#define MAX 10000
// 2156

int max(int a, int b) {return a > b ? a : b;}
int max(int a, int b, int c){
	return max(a, b) < c ? c : max(a, b);
}

int main(){
	int n;
	int wine[MAX + 1], dp[MAX + 1][3];
	
	cin >> n;
	cin.ignore();
	
	for(int i = 1; i <= n; i++) cin >> wine[i];
	
	dp[1][0] = 0; 		// 마시지 않는다.
	dp[1][1] = wine[1];	// 마신다.
	dp[1][2] = 0;		// 2번 마신다.
	
	for(int i = 2; i <= n; i++){
		// 1. 마시지 않는다
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]);
		// 2. 마신다
		dp[i][1] = dp[i - 1][0] + wine[i];
		// 3. 연속으로 마신다.
		dp[i][2] = dp[i - 1][1] + wine[i];
	}
	cout << max(dp[n][0], dp[n][1], dp[n][2]) << endl;;

}

 

해설

1. 마시지 않는다

2. 마신다.

3. 연속으로 마신다.

라는 세 가지의 선택지로 나누어 dp 를 진행할 수 있다.

각 선택지의 점화식을 생각해서 구현해보았다

.