[BOJ] 2156번 포도주 시식 (C++)

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

2156번: 포도주 시식

 

#include <iostream>
#include <algorithm>
using namespace std;

int arr[10010];
int dp[10010];
int n;

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];
	for(int i = 3; i <= n; i++){
		dp[i] = max(max(dp[i - 1], dp[i - 2] + arr[i]), dp[i - 3] + arr[i - 1] + arr[i]);
	}
	cout << dp[n] << endl;
	return 0;
}

 

arr 배열은 각 포도주 잔에 들어있는 포도주의 양이고 dp 배열은 현재까지 최대로 마실 수 있는 포도주 양이다.

 

dp[1]은 한 잔을 마시는 경우가 최댓값이므로 arr[1]이다.

dp[2]는 arr[1]+arr[2] 연속 2잔을 마시는 경우가 최댓값이다.

 

dp[3]부터는 '연속으로 놓여 있는 3잔을 모두 마실 수 없다'는 조건을 고려해야 한다.

  (1) 현재 잔을 마시지 않는 경우   dp[i - 1]  

  (2) 현재 잔 - 1번째 잔을 마시지 않는 경우   dp[i - 2] + arr[i]

  (3) 현재 잔 - 2번째 잔을 마시지 않는 경우   dp[i - 3] + arr[i - 1] + arr[i]

이 중 최대값이 dp값이 된다.