Baekjoon2156-포도주 시식

백준 사이트 2156 - 포도주 시식 문제입니다.

---

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

dp문제이지만 저는 dp를 잘 풀지 못하여 어렵습니다. 저는 다른 사람들의 코드를 보며 참고했습니다.
백준에서는 Sliver1의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

1. input의 최대값은 1만이므로 배열로 처리가 가능합니다.
2. dp문제이고, 3번째 연속된 잔을 들 수 없으므로 3번째 인덱스 기준으로 점화식을 세워야한다고 생각했습니다.
3. 연속해서 고르지 않는 경우도 있다. 제가 생각했을 때 마지막 부분의 점화식은 기존의 합 보다 선택을 가정한 값이 작으면 선택을 취소한다고 생각하였습니다.
   제가 잘못 이해하고 있다면 말씀 부탁드립니다.

---

5. code 및 설명

#include<iostream>
#include<algorithm>
using namespace std;
int dp[10003] = { 0, };
int arr[10003] = { 0, };
int n;
int result = 0;
void Solve()
{
	for (int i = 3; i < n+3; ++i)
	{
		dp[i] = max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i]);		
		dp[i] = max(dp[i - 1], dp[i]);
		result = max(result, dp[i]);
	}
	for (int i = 3; i < n + 3; ++i)
	{
		cout << dp[i] << ' ';
	}
	cout << result;
}
void Input()
{
	cin >> n;
	for (int i = 3; i < n+3; ++i)
	{
		cin >> arr[i];
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	Input();
	Solve();

	return 0;
}

---