백준 2156: 포도주 시식

다이나믹 프로그래밍을 활용하는 문제. d[i][j] 가 i번째 포도주가 j번연속으로 와인을 먹은 상태이고 a[i]는 i번째에 든 포도주의 양이라고 하면

d[i][0] = max(d[i -1][0], d[i - 1][1], d[i - 1][2])

d[i][1] = d[i - 1][0] + a[i]

d[i][1] = d[i - 1][1] + a[i] 

로 점화식을 세울 수 있다. 0번 연속 마셨다면 이전의 포도주 중 가장 많은 값이 들어가야겠고 한 번이면 이전에(i - 1)에서 0번 연속 먹었을 때 두 번이면 한 번 연속 먹었을 때 일 것이다. 백준님께 들은 강의에서 내가 생각하는 경우로 코딩하면 대부분 틀린다고 항상 규칙을 찾고 일반적인 경우를 생각해야된다고 말씀하셨다.

#include <iostream>
#include <algorithm>
using namespace std;
long long d[10050][3];
long long wine[10050];
int main()
{
	int input = 0;
	cin >> input;
	for (int i = 1; i <= input; ++i)
	{
		cin >> wine[i];
	}
	d[0][0] = d[0][1] = d[0][2] = 0;
	//d[i][0] 연속해서 마신 포도주 0잔 ...
	for (int i = 1; i <= input; ++i)
	{
		d[i][0] = max(d[i - 1][0], max(d[i - 1][1], d[i - 1][2]));
		d[i][1] = d[i - 1][0] + wine[i];
		d[i][2] = d[i - 1][1] + wine[i];
	}
	long long ans = 0;
	ans = max(d[input][0], max(d[input][1], d[input][2]));
	cout << ans;
	return 0;
}