ShaShaKa Dev Note

포도주 시식

26 July 2019

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

이번은 규칙에 따라 포도주를 마실 때, 최대로 마실 수 있는 포도주의 양을 구하는 문제를 풀어보도록 하겠습니다.

#include<stdio.h>

#define max(a,b) (((a)>(b))?(a):(b))
#define MAX(a,b,c) (((max(a,b))>(c))?(max(a,b)):(c))

static int** dp;

int main(void) {

	int N, val;
	scanf("%d", &N);

	dp = new int*[N];
	for (int i = 0; i < N; i++)
	{
		dp[i] = new int[3];
	}

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &val);
		if (i == 0)
		{
			dp[0][0] = 0;
			dp[0][1] = val;
			dp[0][2] = val;
		}
		else
		{
			dp[i][0] = MAX(dp[i-1][0], dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = dp[i-1][0] + val;
			dp[i][2] = dp[i-1][1] + val;
		}
	}

	printf("%d\n", MAX(dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]));

	return 0;
}

문제의 조건에 연속으로 3개를 먹을 수 없다고 하였으므로, 다음과 같이 3가지 경우의 최대값이 생길 수 있습니다.
첫번째, 현재의 것을 포함해서 연속으로 0개를 먹은 경우 => 지금 포도주를 안 먹음 두번째, 현재의 것을 포함해서 연속으로 1개를 먹은 경우 => 바로 이전 포도주는 먹지 않고, 현재의 것을 먹음 세번째, 현재의 것을 포함해서 연속으로 2개를 먹은 경우 => 바로 이전 포도주를 먹고, 현재의 것도 먹음 각각의 최대값을 계산해준 후, 3개 중 가장 큰 값을 return해주도록 합니다.