[BOJ] #2156 _ 포도주 시식

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

2156번: 포도주 시식

 

DP를 사용하는 문제이다.

 

DP (Dynamic Programming) 이란?
복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 기법

 

연속 3잔을 마실지 않는 조건으로,

가장 큰 값을 저장하도록 아래와 같이 점화식을 세울 수 있다.

 

1. 현재 기준 0잔 연속 마시는 경우 : dp[n-1]

 

2. 1잔 연속 마시는 경우 : dp[n-2] + wine[n]

 

 

3. 2잔 연속 마시는 경우 : dp[n-3] + wine[n-1] + wine[n]

 

dp에는 최대 값이 저장되기 때문에 4잔 이상이 되어도, 3가지 조건에 해당된다.

 

[ 소스 코드 ] 

#include <iostream>
#include <algorithm>

using namespace std;
int main() {
	int n;
	int wine[2][10001] = { 0, };

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