[백준][2156번] 포도주 시식

Algorithm/백준

[백준][2156번] 포도주 시식

1일1코딩 2020. 3. 22. 23:07

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

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고

www.acmicpc.net

풀이과정

1. dp로 풀었다.

2. 3번이상 연속으로 마실 수 없다라는 조건을 통해 아래와 같은 규칙을 세울 수 있다.

n번째 잔을 먹지 않을 경우, 연속되지 않게 처음 먹을 경우, 직전 포도주를 마신경우 3가지 케이스에 대한 점화식을 구했다.

3가지 케이스중 최댓값이 dp[N] 값이 된다.

소스코드

#include<stdio.h>
using namespace std;
int grape[10001];
int dp[10001];

int solution2(int n)
{
	for (int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1];
		if (dp[i] < dp[i - 2] + grape[i]) {
			dp[i] = dp[i - 2] + grape[i];
		}
		if (dp[i] < dp[i - 3] + grape[i] + grape[i - 1]) {
			dp[i] = dp[i - 3] + grape[i] + grape[i - 1];
		}
	}
	return dp[n];
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &grape[i]);
	}
	dp[1] = grape[1];
	dp[2] = grape[1] + grape[2];

	printf("%d\n", solution2(n));
	return 0;
}