2156번 : 포도주 시식 [C++]

문제 링크

성공 여부(걸린 시간): 성공 (32분)

아이디어

1~N까지의 번호가 붙어있는 포도주를 순서대로 먹는데 3번 연속으로 마셔서는 안되고 최대한 많은 포도주를 먹어야 한다.

연속으로 먹는다는 그런 상태를 관리해주기 위해서 dp 배열을 2차원으로 만들었다.

dp[i][c] 여기서 i는 포도주 순번이고 c는 연속해서 먹은 횟수이다.

 

그리고 문제의 조건이 3개의 포도주를 연속해서 먹으면 안되기 때문에

c는 최대 1(연속으로 1회 마셨다는 것은 포도주 2잔을 연속으로 마셨다는 뜻)까지 가능하다.

왜냐면 2부터는 아예 존재해서는 안되는 3잔의 포도주를 마신 경우이기 때문이다.

 

//연속해서 먹지 않은 경우 (해당 번호에 대해서는 와인을 마실 수도 있고 안마실 수도 있다.)
dp[i][0] = max(max(dp[i - 2][0], dp[i - 2][1]) + wines[i], max(dp[i - 1][0], dp[i-1][1]));
//연속한 경우에 대해서 
dp[i][1] = dp[i - 1][0] + wines[i];

 

c = 0인 경우에 번호가 2가 차이나는 와인 순번까지의 최대값에 이번 순번의 와인을 먹는다는 가정으로 더해서 구하였는데 

여기서 실수를 했어서 몇번 틀렸는데 그 이유은 c가 0인 경우에 무조건 와인을 마신다고 가정을 하고 코드를 짰기때문이다.

 

그래서 바로 이전 순번의 와인을 마셨더라도 이번에 안마시면 c = 0이니까 해당 값들도 반영을 해주어야 한다.

 

그리고 연속한 경우는 비교적 간단하게 이전 c = 0인 경우에서 이번 와인값을 추가해서 갱신해준다.

 

마지막에 dp[N][0]과 dp[N][1] 중에 최대값을 출력해주면 끝이다.

 

+) 그리고 나는 i=1, 2인 경우에 대해서는 미리 처리를 해주었다.

풀이코드

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

int dp[10001][2] = { {0,}, };
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N;
	cin >> N;
	vector<int> wines(N + 1, 0);

	for (int i = 1; i <= N; i++) {
		cin >> wines[i];
	}
	//3 이하인 경우는 따로 처리
	if (N < 3) {
		int result = N == 1 ? wines[1] : wines[1] + wines[2];
		cout << result;
		return 0;
	}
	// 초기값 세팅
	dp[1][0] = dp[1][1] = wines[1]; // 이전 값이 없기때문에 i=3에서 i=1인 dp값을 불러올 상황 대비
	dp[2][0] = wines[2];
	dp[2][1] = dp[1][0] + wines[2];

	for (int i = 3; i <= N; i++) {
		//연속하지 않은 경우에 대해서 최신화
		dp[i][0] = max(max(dp[i - 2][0], dp[i - 2][1]) + wines[i], max(dp[i - 1][0], dp[i-1][1]));
		//연속한 경우에 대해서 
		dp[i][1] = dp[i - 1][0] + wines[i];
	}
	cout << max(dp[N][0], dp[N][1]);
	return 0;
}