[백준] 2156번 포도주 시식

2156번: 포도주 시식

백준 계단 오르기 문제와 비슷하길래 비슷하게 풀려고 했다가 망해서

다른 풀이들 참고해서 풀었다.

 

시작 위치와 끝 위치는 어디든 상관이 없는 대신 3연속 마시기는 불가능하다.

현재 와인이 i번째에 있다고 할 때 그 위치가 세가지 경우로 나누어진다.

 

0번 연속인 경우 -> 0번이니까 현재 와인을 마시지 않는 것이므로 res[i-1]

 

1번 연속인 경우 -> 현재 와인을 마시고 그 전 와인은 마시지 않은 상태이다.

그리고 그 전 전 와인은 마시든 말든 상관이 없으므로 wine[i] + res[i-2]

 

2번 연속인 경우 -> 현재 와인을 마시고 그 전 와인도 마신 상태이다.

그 전 전 와인은 마시면 안 되지만 그 전 전 전 와인은 마시든 말든 상관이 없으므로

wine[i] + wine[i-1] + res[i-3]

 

이 세 가지 경우 중 가장 큰 값을 res[i]에 저장해주고 N번의 계산이 끝나면 res[N-1]을 출력해주면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int wine[10001] = { 0 }, res[10001] = { 0 };

int main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) cin >> wine[i];
	
	for (int i = 0; i < N; i++) res[i] = max(res[i - 1], max(wine[i] + res[i - 2], wine[i] + wine[i - 1] + res[i - 3]));

	cout << res[N - 1];

	return 0;
}