[DP] BOJ 2156 번 포도주 시식 - 오답노트

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

2156번: 포도주 시식

- 문제파악

정수 n과 n개 배열을 주어진다 연속해서 3개를 선택하지 않는 경우중에서 선택한 배열의 합이 가장 큰 경우를 출력하라

 

- 나의 접근

백트래킹으로 풀었는데 시간초과였다.

메모제이션으로 시도 했으나 점화식을 제대로 세우지 못했다.

 

- 정답

D[i] 는 주어진 배열의 합중에서 가장 큰 값을 넣는다. 

포도주를 먹는 경우는 아래 처럼 정리할 수 있다.

지금 안마시는 경우 : D[i - 1]
이전에 안마시고 지금 마시는 경우 : D[i - 2] + arr[i]
지금 마시면 두번 연속 마시는 경우 :  D[i - 3] + arr[i - 1] + arr[i]

 

아래는 위 점화식으로 구현한 코드다.

 

#include "bits/stdc++.h"

using namespace std;

int n;
int arr[10002];
int D[10002];
int ans;



int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	D[1] = arr[1];
	D[2] = D[1] + arr[2];

	for (int i = 3; i <= n; i++)
	{
		D[i] = max(D[i - 1], max(D[i - 2] + arr[i], D[i - 3] + arr[i - 1] + arr[i]));
	}


	cout << D[n];

}