[BOJ] 2156 - 포도주 시식

안녕하세요.

여행벌입니다.

오늘은 BOJ 2156번 포도주 시식 문제를 풀어보겠습니다.

---

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

2156번: 포도주 시식

[알고리즘풀이]

Dp[2][k] 를 정의한다.

Dp[0][k] : k, k-1번 째 포도주를 마셨을 때의 최댓값.

Dp[1][k] : k번 째 포도주를 마시고, k-1번째 포도주를 안 마셨을 때의 최댓값.

 

Dp[0][k] 는 k, k-1번 째 잔을 연속해서 마시므로, k - 2번 째 포도주를 마시지 않았을 때의 최대값이 필요하다.

▶ Dp[0][k] = input[k] + Dp[1][k-1];

Dp[1][k] 는 k번 째 잔을 마시고, k-1번째 잔을 마시지 않으므로, 1 ~ k - 2번째 포도주를 마시는 모든 경우 중 최댓값이 필요하다.

▶ Dp[0][k] = input[k] + max; ( max는 1 ~ k - 2번째 포도주를 마시는 경우 중 최댓값 )

#include<iostream>

using namespace std;

int in[10001];
int dp[2][10001];

int main(void) {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++ )
		cin >> in[i];
	dp[0][1] = in[1], dp[1][1] = in[1];
	dp[0][2] = in[1] + in[2], dp[1][2] = in[2];

	int max = in[1];
	for (int i = 3; i <= n; i++) {
		dp[0][i] = dp[1][i - 1] + in[i];
		for (int j = 0; j < 2; j++) {
			if(dp[j][i-2] > max)
				max = dp[j][i - 2];
		}
		dp[1][i] = max + in[i];
	}
	
	for (int i = n-1; i <= n; i++) {
		for (int j = 0; j < 2; j++)
			if (max < dp[j][i])
				max = dp[j][i];
	}
	cout << max;
}

---