[백준] 2156번 포도주 시식

문제 링크

 

풀이

계단 오르기 문제와 비슷한데 다릅니다. 계단 오르기 문제는 반드시 마지막 계단을 밟아야 한다는 조건이 있었지만 이 문제는 아닙니다. 점화식을 구할 때 d[i]가 i번째 와인인 w[i]을 반드시 선택할 필요는 없다는 의미입니다.

예를 들어 8 5 4 2에서 3개를 선택하는 연속합의 최대값을 구할 때 마지막 숫자인 2를 반드시 포함해야 한다면 5+4+2=11이지만 마지막을 선택하지 않아도 된다면 8+5+4=17입니다. d[i]를 구할 때 w[i]를 포함하는 경우에서의 최대값을 구하고 나서 d[i-1]과도 비교를 해야 하는 이유입니다.

 

코드

#include <cstdio>
int max(int a, int b)
{
	return a > b ? a : b;
}
int main()
{
	const int MAX = 10001;
	int d[MAX] = {0};
	int w[MAX] = {0};
	int N, answer = 0;
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &w[i]);
	d[1] = w[1];
	answer = d[2] = w[1] + w[2];
	for (int i = 3; i <= N; ++i)
	{
		d[i] = max(d[i - 3] + w[i - 1], d[i - 2]) + w[i];
		d[i] = max(d[i - 1], d[i]);
		answer = max(answer, d[i]);
	}
	printf("%d", answer);
}